Arduino Comparison Guide
This Tutorial is Retired!
We have updated this tutorial in "Choosing an Arduino for Your Project." If you are looking to compare specs of different Arduino boards you can view our Arduino Comparison Guide.
View the updated tutorial: Choosing an Arduino for Your Project
jimblom 
ATmega32U4 Boards
The next step in the Arduino evolutionary chain was merging the USB-to-Serial programming part of the board onto the main MCU. That meant we had to leave the ATmega328 behind -- becuase it doesn't natively support USB -- in favor of the ATmega32U4. Aside from the additional USB support, the 32U4 is largely similar to the 328. Both are 8-bit AVRs with 32kB of flash memory, 22-ish I/O lines, ADCs, UARTs, timers, etc.
These ATmega32U4 boards often have the benefit of being cheaper than the ATmega328-based boards -- there's one less costly IC to put on there. They can also do things regular Arduino boards can't, like emulate a USB keyboard/mouse. On the downside, they can be less reliable, and more difficult to use.
Arduino Leonardo
The Leonardo is the patriarch of all ATmega32U4 Arduino boards. It shares the same form factor and I/O placement (analog, PWM, I2C pins in the same place) as the Arduino Uno, so it remains shield compatible.
Differences between the Leonardo and the Uno? Aside from the new microcontroller, and lack of a second USB-to-Serial-converting IC, there's not many. The USB connector is different, the Leonardo connects to a computer via a micro-B USB cable. The driver installation process is also a bit more involved -- sometimes it can take a little extra fidgeting to get the board installed on your computer.
Pro Micro
Just as the Pro Mini took the guts of the Arduino Uno and shrunk them down, the Pro Micro works as a miniature version of the Leonardo. Unlike the Pro Mini, the Pro Micro doesn't require an external board to upload a sketch -- the 32U4 takes care of everything!
The Pro Micro comes in the standard 5V/16MHz operating range or a more unique 3.3V/8MHz variant.
Pro Micros are among the more complicated Arduino boards to get up and running. There are extra steps required to enable them in your Arduino environment, and a misstep can (at least temporarily) "brick" the Pro Micro.
These boards are a good choice if you're an advanced Arduino-er and have a small USB-oriented project in mind (a mini USB keyboard/mouse?).
More Variants!
There are plenty of other riffs on the Leonardo design as well. There's the Fio v3, for any Arduino Leonardo project you might want to add an XBee to.
And there are more unique Leonardo-compatible boards, like the MaKey MaKey, which can turn almost anything (from tin foil to Play-Doh to bananas) into a keyboard key.
The ATmega32U4 can make some very cool USB-integrated Arduino projects.