WarCraft II was among the first games that I ever played "online" (direct connection via dial-up modem with my friends). I can't overstate how absolutely incredible that felt to me at the time - pure magic.

The other games we were playing at that time were Doom II and various other first-person shooters (Rise of the Triad, Hexen, etc) - which were also pretty incredible. But the WarCraft II experience really took things to the next level with far richer gameplay.