This response in particular got my attention:
Check out Speakfreely at http://www.speakfreely.org. It’s Open Source, has versions for both Windows and Linux, and the versions for both OSs can talk to each other. It may be a lot more complic- ated than programs like NetMeeting, but with all the options, you can tweak it to get the ideal sound quality for your internet connection. Plus it has built-in encryption. I’ve used it via 56k modems and while its not quite as good as a normal telephone, it still works great (esp. for the price!). With a faster connection, I’d imagine that you could get better quality than a phone. For new users of this program who are frustrated with lag, I’d suggest changing the Jitter Compensation setting to None so your voice isn’t buffered.