The new version of Google Talk has support for avatars and themes, and perhaps more interestingly, support for BlackBerry devices.
Unfortunately, we don't have BlackBerries here in Australia, so that really doesn't interest me all that much. However, it does seem like an interesting idea - particularly if it's free or very cheap to use.
The avatars are fairly basic. A small 32x32 preview shows up in the contact list, and if you mouseover the person's name a small popup appears, similar to the contact cards in MSN Messenger, which contains a larger version of the avatar.
A whole bunch of (mostly crappy) avatars are available for use by default, but you can specify your own from most image types. Fairly standard.
I like the new theming feature - something that I haven't seen in any other IM client. I think it's a good way to make the interface a little more pretty while keeping it simple and utalitarian - and this is exactly why I prefer Google Talk to MSN (though it doesn't have anywhere near the userbase). You can pick from 9 default themes, some incorporating the avatar into the chat screen, and there's a preview image for each one. My favourite is the ping-pong theme:
I think they're done using some type of CSS. I'll see if I can work out how the themes work and report back here.