I would very much reject KOTOR; its plot was average at best. Morrowind started interesting but then became pretty mainstream and the ending was dire.
Blade Runner probably made a good go at best plot but kinda lost it at the end... darn... but fantastic for the first half.
I always liked Baldur's Gate II myself- David Warner made SUCH a good bad guy, it just went to show that games as well as films benefit from decent personalities.
Prince of Persia was VERY entertaining, also with great characters; I really was not sure about the end, though. Seemed like they just skipped a lot of the strange bits that had been so intriguing earlier on.
Starcraft and Warcraft both had very engaging plots, but I don't think they can be rated for effort along side your Baldur's Gates and Final Fantasies of this world.
Although it did not have a storyline as such, I always found Alpha Centauri's semi-narrative that unfurled as you discovered things very mature and engaging.
For that matter, cheesy as it was, Wing Commander III was frigging superb!
I suppose it is like films; it depends what sort of storyline you are after at the time. Hard to get a decent storyline like the Usual Suspects into a game because the actual 'game' part has to be there somewhere.
A Final Fantasy will probably win it; I just haven't really played enough to judge. I'll shoot for BGII, myself.