I’ve been playing around with a few voice over IP products for my powerbook just recently and it has to be said that some of them are pretty good.
I tried iChat AV as that seemed like the obvious choice because it comes free with Tiger (Mac OSX 10.4) and since I tried it a few times for AIM and Jabber instant messaging it was already setup with a few friends that I could try calling. Unfortunately, the VOIP part seems limited to those who have iChat AV themselves (makes sense), but also you have to be using an AIM login – just using Jabber alone doesn’t seem to let you place calls. I guess this is probably because you can use any Jabber server you want and there’s no way that Apple could guarantee that the server you use is compatible. Call quality was pretty acceptable over a cable modem and it didn’t drop out unexpectedly.
I gave Skype a miss because although it’s encrypted traffic (which is good), it’s a proprietary protocol so you have to use Skype at both ends. Oh, and the company was recently acquired by eBay so there’s no telling what might happen.

Next one on the list was GizmoProject which has clients for multiple platforms (Windows, Mac, Linux) and provides both call in from normal phones and call out to normal phones (same as Skype does).
Using Gizmo, I called the Tellme line which is one of the default entries in the Gizmo phonebook and played around with the voice recognition at the other end. Only later did I notice that it was actually using the 25 cents of free call out credit you get when you sign up. 4 cents, just over 5 minutes, calling the U.S from the UK.. not all that bad really.