Some while ago, shortly after MSN/Windows Live Messenger stopped acting like an IM/chat client and more like a blinkity ad delivery platform*, I decided to look for an alternative.
Trillian supports AIM, ICQ, MSN, Yahoo Messenger and IRC. It's small and fast and I used it for a year before it finally annoyed me for the last time by not remembering my window preferences. It also tended to lose my MSN password more often than I thought reasonable. Still better than MSN by a long chalk.
I just switched to Pidgin this week. It supports *many* (16) protocols including MSN, Yahoo, AIM, ICQ, GoogleTalk, and others I've never heard of, plus it has a fat pigeon icon, which counts for a lot. Pidgin runs on Windows and *nix, and there is a port for OS X. It's an open source project released under the GNU General Public License, and I like to support that kind of initiative. The interface is as fresh and clean as a Spring morning.
* Not just the ads. The following pile of of dung is from the Windows Live Messenger home page. Make a difference by getting advertised at? Uh... no.