For small-size and Arduino compatibility, take a look at the Sparkfun ProMini. Programming the ProMini is essentially the same as for the Uno, except that the programming interface can be removed when not needed. They both use the ATmega328 chip.
The Teensy is extremely cool, but I rarely find myself needing the small size and built-in USB.
Here's a rough size comparison between an Uno and a ProMini. The red board is the FTDI USB-to-TTL-serial programming interface: