Isn't ICQ owned by AIM now? So they are probably the same.
If you're just asking about the service itself, they're all basically the same. Unless there's some special feature you want(video, audio, or something...) there's really no difference. AIM is the most popular, so it'd be less likely that people would have to sign up to chat with you.
Client wise, I've not used either in ages. There are alternative clients to basically any service out there. Trillian, for example, is what I use for AIM, MSN, and YIM. It also has services for ICQ.