If we're talking about web based clients, then I also recommend Meebo and Jivetalk
Agile Mobile just released Agile Messenger for the iPhone, which supports MSN as well as AIM, Yahoo, ICQ and Google Talk
http://www.agilemobile.com
I just got it 2 days ago and it works great