Got a webcam? You should try Eyeball Chat. A friend just told me about it (thanks Donald) and after trying it out, it's pretty spiffy. Beats NetMeeting hands-down. And hey, even if you don't have a webcam, you can still send and receive live audio. I can't say whether or not it is efficient over a dial-up line (prolly not), but it worked great with my cable modem connection. You can even record video messages, save them and send them to other Eyeball Chat users.
The software is free and it's got a refreshingly small installation foot-print (less than 4 MB). No ads, and it doesn't take over your other instant message tools. You can use it to communicate on the AIM, Yahoo and MSN networks as well, but I think I'll stick to Trillian for now for that.