Honestly, I'm not sure. Unlike so many others, my early history with FPS gaming is fuzzy. If I had to guess, though, I would say Doom, Perfect Dark, or Quake 3.
If it counts, Duck Hunt was one of the first games I played period.
EDIT: A really long time ago I frequently played the demo for Thief: The Dark Project. It's first-person and you can shoot (arrows), but I don't know if it really counts. All I ever really did is screw around in the tutorial anyway.