Bioshock comes to mind
No idea why I'm getting downvoted. There are literally only a handful of first person shooters that are story-driven given the great majority that aren't: Quake, Doom, Duke Nukem, Sin, Wolfenstein, etc.
Saying that you miss the "old days" when first person shooters had stories makes no sense other than stirring some misguided Southpark-esque "'member when..." nostalgia.
I mean, if "FPS" means "a first-person game where you often shoot things", then Deus Ex, Bioshock, Half-Life, Thief, Fallout 3/4, Skyrim, etc., can all qualify. Hell, throw in Dungeon Master, and maybe even Portal and Minecraft. Of course one can argue where to draw the line based on how much "shooting" takes place.
But people often say "FPS" to mean specifically "games like Quake and whatnot". Under that definition, shallow gameplay is part of what makes a game an FPS.
That seems to be unfair to Quake - there's a fair amount of depth and strategy involved, mostly with the hogging of powerups. I thought Quake 3 was just a game about two guys bumblebee dancing while trying to shoot the other, until my mind was expanded by a top Quake 3 player explaining his thought processes in the below video - the vast bulk of the talk is about map control, not reflexes.
An FPS has to be a shooter that's in first-person view, but does that make every game where you shoot something with a first-person camera view an FPS? What if the game has other elements? Which definition wins out? Is Fallout more RPG, or is it more FPS? Or is it a turn-based strategy game? Most people would say it's an RPG that happens to have guns and is played in first-person mode and part of the game mechanics is reminiscent of turn-based games.
When you say "FPS", it's a pretty strict definition, because if it's an RPG that happens to be played in first-person with a gun, it's going to be called an RPG first. Maybe RPG-FPS. But FPS really means "run around with a gun and your main interaction with the world is shooting it". There is an entire world of games that do exactly that, and we call them FPS games. Borderlands is an FPS with hints of MMO, dungeon crawler, and RPG, but since the main interaction with the world is running around with a gun and shooting things, it's an FPS. I don't think that's a bad thing.
(The point being, it doesn't mean much to say that few FPSes have deep stories, because if a game has a deep story then people tend not to consider it an FPS.)
You can still have deep games that are Quake-like, Half-Life being the canonical example. Deus Ex can be played, like Fallout, in third-person so I'd say it's disqualified.
Why is HN turning into reddit with random downvotes and no discussion? Must be the weird gaming crowd.
Again, you're talking about the definition, not the thing. Half-life is very Quake-like in its mechanics (camera and controls), and not very Quake-like in its gameplay (exploration, puzzles, etc).
As such, saying something like "FPSes aren't deep" is more about terms than games. Whether you agree with it depends on whether you take "FPS" to mean Quake-like mechanics or Quake-like gameplay.
(Incidentally Deus Ex is first person. The newest ones have a hide-behind-cover feature that temporarily shows you in 3rd-person.)
We're talking about the original Deus Ex which is first-person only.
The most interesting part of that game is Rapture itself, the mnechanics and general gunplay just sucked honestly.