Um, did you ever play quake? If I remember right (and it has been a rather long time) Quake was the first FPS to have no plot at all whatsoever, not even alluded to in the manual. There was no opening cutscene, no text of any form at any point in the game, and in fact the start of the game was somewhat unique because instead of having you select difficulty from a menu, they instead dropped you into a room with 3 portals, one for each difficulty.
Wolfenstien had a plot. "Escape from castle Wolfenstien, and kill nazis". Doom had a plot. "Aliens destroyed earth and you have invaded their base and must kill them all". The plot interaction consisted of showing you the name of the next location you were attacking, and some text when you completed the episode. Oh, and you could read about the atrocities of the aliens in the game manual. Heretic has a plot with the same mechanics. Doom2 likewise. Duke3D used a plot similar to doom, except the fight started on earth. Duke3D actually had things you could interact with, but I wouldn't go as far as to call them plot elements. Quake had no plot. Quake2 had an intro plot (same used in Doom) and even an engine-rendered cinematic, but then reverted to killing everything in sight for the rest of the game, like quake 1.
Half-life was seriously the very first game I ever played which was a true fps with rpg elements. Half-life broke new ground.