I was using ICQ 99b as it had all the new features I wanted, but none of the annoying ads or useless crap yet. Recently they decided that they didn't like people using older versions, and it would drop a ton of messages. When it got to the point where I could only send one message to a person a day, I switched to Trillian. It's probably just because I'm used to ICQ, but there are a few little things that bug me about Trillian, but overall it's pretty good. Especially with all the different chat programs it can replace...
For you paranoid types, you can also have SecureIM conversations between Trillian clients. Your conversation is encrypted, so you don't have to worry about those damn pinko commie nazi viet cong reds intercepting your cybersex. Or something.
AIM users might find
http://toc.oscar.aol.com handy too. I've had weird issues where it says the right login/password is wrong, but it seems to be only on Win95. If you're using Mozilla, you have to allow Javascript to open unrequested windows for it to work too.