For me, it would be Valkyrie Profile, (or Valkyrie Profile: Lenneth). This game was fun to play, but it got kind of stupid on the second disc. The way to get the A ending is so fiddly that it is almost impossible to do without a guide book or a Faq in your hands. On top of that, the three endings are really just logical progressions of your actions. I guess that the game lost me when I realized that Valkyrie (Lenneth, Silmera, and ?) were just programs that attached themselves to the deceased woman and nothing more than that.
Xenogears had the best plot, but the worst execution. The paceing on the first disc was good, tell the player where to go and allow him to get there on his own volition. There were some puzzles that were exercises in controller breaking frustration. But there were many nice reveals in the couse of the game, like what Fei and Elly really are, what the world is and so on. Then 4/5ths of the way in the first disc, the game goes into railroad format and you see scene, play a bit, see new scene, and repeat until 3/4 of the way in the second disc. I still think the game had a great plot, but the execution was terrible.