ICQ was cool at first, but then it started to become bloated with useless features and unnecessarily complicated as a result. I switched to msn pretty quickly.
What was great about ICQ is that it was the first IM system(IIRC) to get reverse engineered and have third-party clients for it that were far better than the official one.
I remember being able to IM people from anywhere with a terminal program.