I think that the core and some of the libraries have been ported to AVRs as small as the ATtiny85.http://code.google.com/p/arduino-tiny/
I don't think the tiny's support a bootloader.
Note that from a hackability point of view, a mega8 has compete Arduino compatibility, and is less than $1 more expensive than a tiny85...
(actually, a tiny85 isn't so tiny. 8k Flash! So it might be more capable than I'm thinking.)