DOOM was the first MP experience over my high-school's LAN (never could get direct-connect via modem to work); but that was ended pretty quick once the teachers found out.
A few times a friend and I tried Command & Conquer over dial-up, but it was always such a PITA to connect so we gave up. Then I started using KAHN for MP; but by that time GameSpy was catching on and a lot easier to use
My first "real" online MP experience was Half-life/Team Fortress...on dial-up
Let's just say I got killed a lot