http://www.google.com/talk
I knew it was only a matter of time before Google made their own IM client.
You need a Gmail account to use it, but Gmail is open to any sms-compatible phone now. (invites are a dime a dozen nowadays anyway)
I tried out Google Talk, but it was a bit bare imo. Luckily it uses the Jabber protocol which makes it compatible with many other chat clients.
Google Talk supports standards-based communication clients, which means that Gmail users can access the Google Talk service and exchange instant messages using other clients that support the standard XMPP protocol, such as Trillian, GAIM, iChat, Adium, and Psi. This allows users to access the Google Talk service for instant messaging from all major platforms, including OSX, Linux, and Windows.
It's not bad, a refreshing change at times from the somewhat bloated msn etc
If you want the bare minimum, try Miranda IM (http://www.miranda-im.org), which is a multi-purpose IM client such as Trillian, but not bloatware like ICQ, MSN or Trillian itself. It also supports XMMP/Jabber :)