Duke Nukem 3D and Doom over modems. When I got the 'net, it was Quake over a shite modem connection. Later I dabbled with the Aliens Online game, which wasn't much fun over dialup.
And then my friends started having LAN parties. Quake, Hexen, Duke3D, Warcraft... The awesomeness of the Quake Superhero mod is difficult to describe with words. "Ants in the Pants" in the lava-filled DM map was a griefing joy.