Heavy Rain. The personalities are a little weak but the plot and storytelling techniques are Hollywood level.
The first Dragon Age has some really powerful personalities, but the overarching plot is a little bleh.
Valkyria Chronicles has a good bit of epic storytelling but the personalities are, again, flat.
Skies of Arcadia has some awesome personalities and plot twists (and music) but the gameplay is a bit dated now.
My standards are very high when it comes to storytelling, so that's really all the games I can think to recommend.
Hmmmnnrgh.. (how do I disagree without sounding like a pri- oh my god I'm typing out my inner monologue again o_o)
If Thousand Year Door is the one with Peach and the computer, I'll agree to a point. That little side story was unexpectedly touching. I also kind of disagree with Viewtiful Joe. It was alright I guess. A little whacky. I agree with The Author about Fallout 3 being a good story but it's really brought down by bad storytelling/voice acting/animation/etc.