Skype has been out for a couple of months now, but I only recently had a look. I have never been very impressed with the audio quality of these various voice-chat systems. However, Skype is a whole different story. With similar-looking clients for Windows, Linux, OSX and PocketPC, a mechanism called SkypeOut for making calls to regular phones and some nifty P2P principles applied to the problem of getting in and out from behind firewalls and NAT gateways all combining to create something that works extremely well for most people. The biggest problem people generally have with it is figuring out how to get a microphone installed and configured for their systems.
I installed it on a machine at home before heading to Paris and have been using it to talk to Christine from Paris. I also got my parents to install it by themselves and have had 3-way conference calls with me in Paris, my parents in Toronto and Christine in California. I have also called landlines in the US from Paris and Christine called my hotel landline in Paris using Skype. Overall the quality of all these calls were amazing. Every now and then there would be a slight drop or when 2 or 3 people all spoke at once it would occasionally garble things, but it is definitely the coolest piece of software I have used in a while. Although I may have to invest in a headset for it. You get some strange looks when you sit there talking to your laptop.