I never really bothered with multiplayer in Doom and Doom 2 until the Quake days, and I did a few modem games with a nearby friend. It was back when you set it up so that one person's PC dialed and the other waited for a ring. I played a shit ton of Duke Nukem 3D that way, as well as Warcraft 2.
I bought Quake hen it came out, and my PC didn't play it well at all. Same with Diablo. I got disheartened and sold my PC for $500 and bought a car with the money. I ended up getting Diablo for PSX haha, and I've still never beat Quake 1. (though I had it for N64 at one point)
I think my first gaming over the actual internet wasn't until Diablo II. Well, it was the first one I played a lot of online. Thinking that far back I can't remember what other games were already out, but I do remember using Gamespy way back in the day.