Is it true that the ATtiny AVRs have no hardware support for multiplication? It seems to work fine as I do multiplication in my code. I've also included math.h and have a couple of sin() and cos() calculations. Am I running into some huge 800-cycle penalty for these calculations, does anyone know?
The ATtiny does not have a hardware multiplier, but software multiplication is not quite as expensive as you imply. See the AVR200 application note and associated code for some optimized multiplication and division routines.
Sine and cosine calculations can be accelerated using lookup tables, effectively trading memory space for processor cycles. However, as @DaveTweed correctly pointed out, algorithmically approximating sine and cosine in software will push the cycle count up nearer the range you fear.