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.