ICQ is old school. Are there public chatrooms in ICQ? And I don't know much about AIM, so same questions apply.
Trillian actually does IRC as well, but I think you need the premium version. I've been using Miranda for MSN and IRC together. At home I just use a java applet on a website (we can embed the applet on a page here on ProductWiki).
Right now it's looking like we'll go with IRC. Jan has actually set up A LOT of stuff already, and nobody has really said anything that bad against it... I want to hear more about ICQ/AIM. The big hurdles with those are that they require you to install software. Even if it is just Trillian or Miranda. But it might be worth it.