Trillian is an application with a horrible interface, but works with MSN, AIM, Yahoo as well as ICQ. If you don't mind limited 450 character messages, uncustomizable text and no filetransfers, and no message style toggling, then trillian is for you. Otherwise, avoid it like the plague.
If you want a very decent ICQ replacement, use
Miranda ICQ. It has nearly everything you could possibly want in an Instant Messenger, and it's apparently compliant with MSN as well - it is a 200KB download, to boast. The latest AOL/Mirabilis ICQ client is actually quite excellent. You may download that from ICQ.com. It is fast and efficient and you can tweak it to have very little bloat yet you have all the good messaging features and file transfers, chat, etc. Only problem is if you have a very small amount of ram, it still eats a lot of that.
So, if you are looking for a program with an ICQ-like interface, or an AIM-like interface, that you can message both ICQ and AIM users with.. I hate to burst your bubble, but you aren't going to find one. If we (group of people working together) actually go through with our IM project, then we will be creating an msn/aim/icq compatible client with a nice interface, no short messages, etc.. but until then I believe it doesn't exist.
-RSI