Another great example is Team Fortress 2. All the characters are carefully designed to be distinguishable at a glance - I remember seeing a great explanation of this a few years back, but can only find this pdf right now:
It's all about the distinctive silhouettes of the character classes and how they move. Even with clothes you can quickly recognise a heavy, a pyro, a medic at a distance.
It's a lot harder though. The larger hats breaks up the silhouette quite a bit. At least you can still identify based on posture, which is done pretty well.
http://www.valvesoftware.com/publications/2007/NPAR07_Illust...