Skype: The ability to conference call is great, but it seems like the audio quality suffers a bit when multiple people are involved. There's also a bit of lag at times. Voicemail is only available with a subscription. The VSkype plug-in for webcams is a nice feature. File sharing works well, but can interfere with the your audio quality as it uses up bandwidth.
Gizmo Project: Voicemail is free; files are delivered by email. The hold feature is amusing — choose your favorite awful sound file and annoy the person on hold just like it's a customer service call. Gizmo sounds a little better than Skype, but it seemed like making a connection took a bit longer. We haven't tested the conference call feature yet.
Yahoo! Messenger: Lots of features means you'll need lots of RAM. This program seems like a resource hog, but it's hard to argue with the results. Messenger does instant messenging very well and integrates voice nicely, too. The selection of emoticons is OK. The "audibles" are more fun, though that could wear off. Some will not only like the audibles, but the ability to play games within the IM window. Messenger also has a very nice photo sharing feature and offers the ability to stream a webcam (not yet tested). File sharing works well, too. Voicemail is stored within the program.
Google Talk: It's brand new and lacks many of the features (conference call, voicemail, etc.) other programs offer. The upside is that you barely notice the program when it loads and runs in the background. We haven't played with this yet, but I've read some reviews that claim the audio quality surpasses what the aforementioned programs deliver. I do like that Google Talk is integrated with Gmail and can notify you of new mail.
At this time, I'd say that Yahoo! Messenger offers the most options and works well. You'd better have the system for it, though. If you're looking for simplicity, Gizmo Project or Google Talk would be the way to go. If and when Google starts to upgrade Google Talk, watch out. Chances are they will blow away the rest of the field.