I'm not near my Arduino (acutally, it's an Olimex board with an Atmega168 in a ZIF) right now but I did try ints instead of longs and saw no performance increase. Given that millis() looks to be expensive, I will rewrite the code when I get a chance, and have it do a skad of operations and check the millis() after it and divide by the time (instead of calling millis() several times for EVERY loop). Thanks both of you for your help.
In the end I'll probably end up using a 555 timer for my 100 KHz application, since it won't actually need any configuration. But my first thought had been "I'll bet I can get an Atmega8 to serve as a cheap, precise arbitrary square wave generator."