I didn't quite understand the concept of the perfect story-based game you described. Is it a non-linear story with tree branches? Then the first things come to mind are
The Pandora Directive,
Cave Story,
Blade Runner and
The Last Express, of course.
While the first two are definitely on my top list, the last two are not, which doesn't make them any less important and/or revolutionary for the industry, that's for sure. I just value the gameplay too much.
Otherwise, I can come up with my own examples of games where stories were so immersive it felt like you were making them up
But isn't that a bit unfair and too subjective?