I have no idea what the first FPS with emphasis on story was, but I do recommend already mentioned Clive Barker's Undying and No One Lives Forever (though that one is 80% stealth 20% shooter).
Edit:
F.E.A.R. games also have an interesting narrative, but in terms of gameplay 95% of the game is shooting stuff.
TheMonkofDestiny: Heretic and Hexen
From the original post I would say that is not what StingingVelvet is looking for, at least on Heretic 1 part.
Heretic is essentially a Doom clone in different setting with some nice details added (inventory and flying), but fundamentally it plays exactly like Doom. Hexen is a bit different and heavy on exploration, but in principle isn't all that different from Quake 2 in terms of design and there really isn't that much story. Hexen 2 may be an interesting middle ground though.
TheMonkofDestiny: Also, as an aside - I had to laugh a bit at the thinking of Quake 2 being more than Quake part. Mostly because it's the divide of that series. People who loved the style of the first dislike the second and often vice-versa. Quake 2 is a fun game, but it's no Quake as far as I'm concerned. I keep hoping one day Bethesda and id will go back to that well and pull something interesting out of it similar to Doom 2016 or the Wolfenstein reboot (up to a point, at least).
Funny thing is, there are elements in both these games that I like and can't stand. I am one of (very few from my observations) people who liked gameplay and design of Q2 much better than Q1. I loved the hub system, I felt the guns felt better, levels were more open etc. But for some reason they decided to put it in the most bland setting imaginable. Q1 I think had the best atmosphere out of all id games. The setting was great, the music was great, but I always feel there was something missing in the gameplay department.
I would love to see a return to that Lovecraftain setting, preferably with a more serious tone and not the Doom goofiness.