I love a good story. When I first played Ninja GaiDen, I was blown away! The cinema screens were very intricate for their time, and the music only added to the intensity. There are quite a few great NES games with story lines pounding the game forward. What comes immediately to mind is Vice, Golgo 13, and, of course, Final Fantasy. If these games didn't have stories, they would just be some other run-of-the-mill games that sold xx amount of copies, and were just ok games with good play control. The stories... helped make them great games!
I'm not too sure if this fits, but Kirby's Adventure had a great, lengthy story that allowed for great villains and game play. Fictional gaming at it's best.
Final Fantasy III's story was pretty good.