I used to always use Trillian for my instant message needs because it was slick and small, didn't have ads, and did pretty much everything I wanted - I even paid for the professional version (twice! once for 2.0 and once for 3.0) because I liked it that much.
But the new Live Messenger is pretty cool. Whereas MSN messenger (the old ones) is pretty much unusable (who in the world would want to use a client program so cluttered with useless UI?), this new one is much better designed and actually looks good! And it's usable. And it has quite a few new features.
Now if only they would sell one with no ads, then I would be happy.