Discounting our NES friends since there was never really any pressure to even have a story back then, I'm going with PH, straight up.
Here's PH's plot:
...
...you ready?
...
"There's an evil squid. It kidnapped the princess, and killed some whale guy. Collect X magic things to kill it."
I mean, really. PH's story had less going on than LttP, for god's sake. At least LttP gave you the Agahnim=Ganon twist at the end and turned everything on its head with the Dark World in the middle of the game. OoT at least had the Seven Years of Darkness and Ganon's takeover. Hell, even Link's Awakening, which never really gave you any story except in the beginning and end, at least had memorable characters and events to keep you caring about your mission.
But PH? The only thing that could count as any kind of twist is when Oshus just magically shows up on the evil Ghost Ship with no explanation as to how he got there, and tells you that "yeah, I was just pulling your leg- those fairies were useless, what I actually need is some metal for a sword", which is an excuse to stick to the Rule of Three and prolong the bland game. Pretty much from start to finish, nobody gives a damn about anybody in the world, because when they're not being boring, they're being damn annoying, and if Tetra weren't conveniently kidnapped, nobody would care about the stupid, stupid squid.