gAIM is my new best friend
I remember gAIM being just a "linux-only" thing which I did use off and on in the past. When I tried it before, it was okay at best. It didn't really work on Yahoo that much and the interface was a bit on the large side (icons were freakin' huge).
I tried it again today. Everything's fixed now. Icons are proper size, interface is easy, tabbed windows are a dream to work with (truly), and it's just plain cool. I have officially switched from Trillian to gAIM. It's small, clean, works with ICQ, AIM, Yahoo, MSN and several other clients really, really easily. Cool beans.