I would like to recommend Nimbuzz, a great VoIP substitution for Skype, as well as a stable, classy, beautiful and simple alternative for Windows Live Messenger, Yahoo Messenger, Google Talk, and even Facebook chat. It is certainly one of the more appealing (recent) messenger apps I have discovered recently. It is available for both PC and Mac, and of course mobile phone/tablet platforms, and even as a web app that can be used in any browser! Nimbuzz: Download Messenger| Free VoIP, Cheap PC to Mobile Phone Calls
The PC version lacks certain messenger features (such as video chat), and the developers plan to include them in future versions, but so far, the app works great!
Highly recommended if you can't use Windows Live Essentials 2009 anymore due to Microsoft forcing you to upgrade, and you don't appreciate the 2011 release.