Funny story, the first time I played a multiplayer FPS deathmatch, it was in 1987! It was at an Atari convention (back when the Amiga and Atari ST had the best graphics/games around). It was really innovative thinking, considering the ST (or the Amiga for that matter) didn't have network connectivity built-in. They used the midi-IN and midi-OUT jacks to create a daisy-chain network that the game could talk over. Hence the name : Midi Maze.
It was hilarious and fun, but man is it dated now. I think I played an eventual remake on the Gameboy but it's still cool to think of it. I think it was the first time a multiplayer FPS was available on consumer hardware.