The question "which flash should I buy for my camera" comes up about twice a day, so I thought i'd write an FAQ to tell everyone the basics. If anyone would like to add more info to this thread please do, i'll merge all information into this first post. If anyone has questions please put them into a new thread rather than cluttering up this one.
The way I think about it there are three classes of flash: Canon, ETTL compatible, and everything else. Canon flashes are always the safe bet, they'll work with any EOS camera now or in the future, and the quality's very good. ETTL compatible flashes are designed to work the same way as the Canon units, their main advantage is usually price (though not always). Other flashes weren't designed to work on EOS cameras, but many with an auto mode will work fine. For most people, the best advice is "buy the best Canon EX flash unit you can afford", but other factors can change this.
Buy the 580EX if you can afford it, the 430EX if you can't but want a good flash, a 550EX if you need the power/wireless master at a better price, or a 420EX if you want a cheap, simple flash that will do the job well. See more details below.
The best Canon flash is the 580EX. It's the most powerful, has a full manaul mode, the controls are easy to use, and there's only one button to rotate the flash head in any direction. It's a wireless master, so it can control any other EX flash unit without wires. The 580EX is relatively new, so all the latest advances are found in it, such as a faster charging rate than the older flashes, and it has a small white bounce card which pulls out from the flash head. It also has a wide angle panel, which I think all Canon flash units have. The 580EX has a high voltage input port, which can cut your recharge time down from around 6 seconds to 1-2 seconds, depending on the external battery used.
The next model down is the 550EX. The 550EX is a little older, is effectively just as powerful as the 580EX, but there are two buttons to rotate the flash head in different directions. It has a full manaul mode, recharges a little more slowly than the 580EX, and the controls aren't quite so easy to use. The 550EX is also a wireless master, and also has a high voltage input port.
The 430EX is the little brother of the 580EX, and is currently the newest Canon flash unit. It's about one stop less powerful than the 580EX, doesn't have the built in bounce card, and is only a wireless slave, not a master. It has the single button to rotate the flash head. The 430EX has a full manaul mode.
The 420EX is an older unit, similar to the 550EX, but less powerful, and it's a wireless slave not a wireless master. It has no manaul mode, so it can only work in ETTL. This is only a problem if you want to use your flash as an optical trigger for studio lights, as the ETTL preflash triggers the strobes too early. This flash is an ideal flash for someone who wants a cheap easy flash unit for not much money, or for multi-flash setups.
So which flash unit should you buy? If you can afford it, and want the best available, get the 580EX. If you don't want to spend so much, don't need the power, or don't mind not having a wireless master, get the 430EX. If you want the extra power or the wireless master function at a cheaper price, get the 550EX. If you need a cheap, simple, but effective flash, or a wireless slave, get the 420EX.
The Sigma 500 DG Super has a good reputation. It's basically the same as the 550EX, just cheaper, and some say the build quality isn't quite as good but it's fine. The Sigma has an optical slave, which could be handy for some people, but remember that if you try and trigger it with your camera flash the ETTL preflash will stuff things up. The Sigma reportedly does wireless ETTL as both a master and slave.
The Metz units (thread 1, thread 2) have excellent reputations. One advantage of them is they have an auto mode, which is meant to be more consistent than ETTL (thread 3). I've read that the sensor is near the flash head, which makes it difficult or impossible to use a diffuser in auto mode.
See also this thread.
(This section will hopefully be filled in by someone who knows about other flash units).
http://www.shootsmarter.com/infocenter/wc031.htm (free registration required, this is a great site)
Non-Canon flash unit discussion.
EOS Bible recommendations.