I tried Fring and Viber. Both good. Fring seems lighter and more performant and you can use it for MSN chat too.
Viber integrates very well into your phone contacts.

Skype is the "standard" and is not so bad actually, only some version are unstable. A nice thing about Skype (besides everyone having it) is that you can be logged in on say both your PC and mobile, and if someone calls you it will ring on both devices and you can pick up on any of them.
Fring is for Israeli. Blocked in Lebanon by court decision.
Others... well, XMPP+Jingle and SIP - rocks. Sorry, in Lebanon - SIP over TLS :-)
any voip application for blackberry ?? (tested working well !)