Another I remember from that era was Microsoft Netmeeting.. there was an screen with a list of all users and their status online/offline and you could call a random stranger.

Another thing I remember about this is that I could make unlimited calls to land lines in the United States from my country. Pretty interesting for a 12 years old kid.