You want a really well-done game that was uncontroversial? Half-Life. Before it came along, all FPSes were mindless shooters with the barest modicum of story to act as the "reason" for killing everything in sight. (ignoring that most modern FPS games are trying to go back to that...) Half-Life injected a game world that felt alive, and was rife with story and plot, even if to get much of it you actually had to listen to the people around you... And it gave you allies, two enemy factions that were also at war with each other, and actual reasons to go where you ended up going. Only once you get to Xen does it feel like the game's quality takes a dive, and that's due to suddenly limiting you to basically everything that you'd find in other FPSes: a path to follow, everything is always your enemy, no plot growth or advancement...
I see your Half-Life and rise you a N64 Goldeneye that came 1 year before. You couldn't just barge in shooting everywhere, there were often hostages, civilians, valuable cientists and key equipment that could easily be destroyed by a stray bullet. You had to ask questions first and shoot later. You had to get creactive with your limited equipment to get out of tight spots. Several levels had open areas to explore, with the objectives put in random positions so you couldn't just memorize them. The only case I rememember where you pick an half-assed movie and get out a legendary game.
There were also no miracle medic packs or super regeneration, so if you ate a bullet, you had to deal with it for the rest of the level. There were valuable body armors here and there, but they could also be destroyed by stray fire.
Also higher difficulty didn't meant just stronger enemies, it also meant more and stricter objectives. Before you could afford to "collateral damage" three scientists, now you can only one.
And it kept that quality all the way to the second-to-last level (protect Natalya, find the best way to destroy the armored mainframes, stay alive against far superior forces). And in the last level you got your showdown with the big boss. And then not one but three extra missions to unlock.
Did I mention the part where you can drive a tank trough Moscow crushing puny soldiers under your iron threads? Enphasis on "can", you could also go in foot, which did make you a much smaller target for the enemy anti-tank weaponry.
