I think kill.switch and even Winback on the N64 did the whole 'go flush' thing ages ago, too.
To be honest, I doubt there's been a single non-RPG game with a truly great story (and even then, they're rare in RPGs; KoToR 1 is the only that comes to my mind, and even then it's a well told but generic version of Star Wars: A New Hope).
EDIT; there have been some good 1st generation games; Mario 64 springs to mind, or Super Mario World on the SNES (not buying a Master System, Megadrive, PS1, etc at launch, I'm not sure about their launch lineup). Of course, nowadays it seems games are measured on presentation - show over substance - which is the only area where you could reasonably expect 1st generation to fall short.