Arduino Comparison Guide
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.
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.
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!
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?).
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.