Too Simple:

FFX --> Being completely objective, I've never disliked a protagonist so much as Tidus. Really, I wish I could've played as someone else in the main party 99% of the time. I'm sorry. Most of the heroes in that game (and a good portion of the story) were cliche to ridiculous degrees. I think Wakka and Lulu were the most interesting people in the entire game, and was disappointed that the plot had to revolve around this guy that I tried so hard (so hard) to like. I don't think Kimahri received an appropriate amount of character development. Most of the time, he was just there. I don't think there was any real attempt to give him an honest backstory. I know this isn't related to the story, but am I the only one who noticed that Lulu was more useful than the hero in battle a majority of the time? Alright, I'm done. Despite this, I still enjoyed the game. It was beautiful and I liked the camera angles (although I often had to rely on the minimap to avoid getting stuck).

Pokemon Black/White --> I don't know if it's too simple, but I disagree with the plot. They made the liberation of Pokemon seem like the most evil thing imaginable and, in reality, I think the only thing that made the villains...er, villains, was the fact that Ghetsis was just using them to gain power. Aside from that, what? I mean, Team Rocket in the earlier games used Pokemon for evil doing, so you wanted to stop them. You felt like you had a legitimate reason to do so. But here, it's the premise that bothers me. If it weren't for the ulterior motive of Ghetsis (which isn't revealed until the end of the game, which means you're fighting the liberation of Pokemon up to that point), the plot would've given the player absolutely no reason to oppose Team Plasma. What happened to Pokemon...? I guess I'm just disappointed because I grew up playing Pokemon games, and now they're just...I don't know how to describe it, different from the way they used to be. Still, I could appreciate the various new and interesting features in the game.

Just right:
Zelda
Golden Sun

Agreed!

Also just right are the earlier Pokemon games. Basically, everything before Black/White was released. Even though the protagonist in Pokemon Colosseum had a sketchy background, he still ends up saving Pokemon throughout the game from a group that had decidedly worse intentions for them.

I know this isn't related to the story, but am I the only one who noticed that Lulu was more useful than the hero in battle a majority of the time?

Rikku is actually the most powerful character in the game. You can beat the whole game (excluding optional bosses like the Dark Aeons) using only Rikku and never even touching her Sphere Grid. Using the Sphere Grid and playing normally, Lulu and Wakka are the second strongest characters after Rikku due to their incredible accuracy, elemental attacks, and debuffs (Sleep, Poison, ...) unless you're facing one of the rare enemies resistant to magic, in which case Lulu becomes pretty useless. When you reach the damage cap (initially 9,999), Lulu actually becomes on of the worst characters because her magic is too slow, and Tidus becomes one of the best characters because of his fast attacks. In endgame when all your characters' stats are maxed out, the only practical difference between characters is in the Overdrives and the Solar Weapons where Wakka's Overdrive is the strongest attack in the game, Tidus's the second strongest, and any third member in your active party would not need a damage dealing Overdrive because passing their Overdrive to Wakka (or Tidus) would do better damage. So Rikku would be the best choice for a third party member because of the versatility her Overdrive offers when needed (or Yuna to summon Aeons to take a blow for you). Lulu, while strong for most of the game, actually becomes one of the weakest characters in endgame (if not the weakest). I played that game too much not enough. :P

Back on topic.

Too complex:

Metal Gear Solid 4, and the whole saga from there on (to the point where I don't care to follow at all anymore)

Final Fantasy XII

many modern "western" RPGs that drown you with background info completely irrelevant to the plot

Too simple:

........can't really think of any. Pokemon Red/Blue/Yellow? I would have liked more story in those games, I think. Never played any other games in the series, so I've no idea how that evolved.

Just right:

Mario Bros. series

Dead or Alive series

Final Fantasy series

Donkey Kong Country series

Tetris

Bastion

Transistor

....too many to list. Probably all the games I've played that I haven't mentioned as having too simple or too complex a story.

I actually don't think you can have too complex a story. To quote my friend Jeff Vogel (Spiderweb Software, and many games you may consider too complex) - Story is fine as long as you let your players ignore it.

That's the key- When a story goes wrong is when you force it down your player's throat. As long as you support however much they are willing to get into your complex storyline while allowing them to basically "opt out" of it you're in good shape regardless of how complex the story becomes. In fact, I feel a sufficiently well written and complex, conversation inducing, story helps give longevity to games - because you can forgive a game for outdated graphics and a great plot.

You can also have too little story (or no story) and do just fine, as long as the story isn't your selling point :) There's no shortage of games with no story and many have already been named here.

When it comes to the best game story ever written I have to go for Star Control 2... So there's my vote for what it's worth!

The "simple story" depend on point of view that "story" covers. As a simple story game would definitely be considered MDK, but also game Sacrifice is story-none, but you can pick from as much as 5 gods to play for, influencing your hero and army, would that count as no-story game?

But games that are truly difficult in story-set from any angle of view, would be Gothic1, Gothic 2, TES3:Morrowind. Also games that invest in narrative a lot (dabing, acting etc) would be story rich, though they would not posses the classic rpg style of modifiable story-tree.

Just right:
Zelda

Just right:
...

Tetris
...

This has got to be my favorite part of this whole thread.

More for the Just Right:

Advance Wars series

Fire Emblem series

This definitely is dependent on genre of game. And what you consider story. Even though some games lack a lot of dialogue, you still get some story through actions/events that have taken place through the progress of the game, such as defeating certain enemies/bosses or getting to certain areas.