Well, here's my roundup...
GAIM is my latest favorite, like has been said, it supports everything (pretty much). It also works well with people on the other end using winbloze, and is very easy to configure and use.
I used to use Everybuddy, but it wasn't very user friendly, needed constant updating, and didn't have the universitality of GAIM to me.
I have used ymessenger, and it works just fine, but only supports Yahoo! messenger.
So like the rest, GAIM is my suggestion.