Skype is Internet telephony developed by some of the KaZaA originators. It launched with a lot of fanfare a couple of weeks ago. The advantages they claim are NAT traversal, high quality, and encryption.
I just tried it out with Scott and was impressed. Installs with no trouble and no scumware. Looks like an instant messenger app. The voice connection to Scott just worked. The sound quality was great even with our crummy desktop microphones. It was only half duplex, but that may just have been one of our sound card setups.
The network details are good too. Despite us both being behind NAT routers we got a direct P2P link going at the click of a button, no configuration required. Traffic was a steady 11 kbytes/sec (just perfect for my 16kbps link). The packet trace of connection setup is a bit odd - it talks to a bunch of different IP addresses. But hey, it works!