The best storytelling games have always been adventure games of the point n click variety like Monkey Island and ESPECIALLY RPGs, most notably the ones that allow you to modify certain plot points, essentially writing your OWN story to a degree.
I can't agree with the Amiga being a high point for narrative. That is for PC (Day of the Tentacle aka D.O.T.T etc!, Fallout, Planescape) and for console RPGs like Chrono Trigger (SNES) and Xenogears (PSX).
The biggest problem with story telling in games these days is what I call the "Rail Road Effect", which is basically the player sitting their passively being TOLD what's going on and not having any choice in the matter (most JRPGs). I guess my opinion is "narrative in games is over used" (cutscenes = the suck!).
Most of the greatest games don't need stories of course; they're just have great game play. See - shmups, a fave genre of many hardcore gamers. :-)