Skype is a particularly difficult piece of
malware software to replace. There are no alternative free software clients, and the protocol itself is non-free.
However, now, thanks to http://jabbim.com, everybody can make a first step away from MS Skype.
Jabbim.com has been around for years providing a Jabber server with a large number of additional services. Most of them are free, while some require "VIP membership", approx. 7 € a year.