ICQ went down the same path most clients seem to go, ie. it got very bloated. At first it was very bare-bones, with some really pleasant file transfer capabilities.

Skype really is history repeating itself. The client is becoming less usable by the day, and for some reason I was selected for a beta test that introduced the "new" flat style, at a huge cost to layout efficiency. It's truly terrible.