This actually connects to my problem with Gen V: the starters.
Indeed, I fully agree that of all the Pokémon that should be designed to deliver a fun play experience, the starters are the most important by far. These are the Pokémon that the players will feel the strongest connections to, and they are likely to stick with them for the entire adventure. It's important to tweak their "power curve" to match the "progress curve" of the games. Just as - or a little before - the game steps up its difficulty, and in-game opponents will start to use tougher Pokémon, your starter should evolve for the first time. This should put its power above what is needed to progress, and the starter should be able to carry the team through any immediate difficulties (such as Gym Leaders). This should repeat again upon the next evolution - the Pokémon gets a power boost around the time you start to need it. Maybe this could also be extended to envelope Mega Evolutions, though at the point in the game when those become an option, your team isn't as reliant on the starter any more.
The starter should, however, not be totally overpowered. Strong enough to pull its weight, yes, but not so strong that you'd never need to use anything else. There should be a point in the game where your starter simply can't do the job alone. This is quite hard to design for, seeing as you get to choose three different starters in every game, and their traits form a rock-paper-scissors triangle of what they can or can't be used for. BW attempted to do this with Striaton Gym, which I guess is an alright way to do it. Early-game is where it's easiest to place difficult hurdles, and where passing them is the least time-consuming - you simply catch the right Pokémon for the job, and train it up to par in a few minutes. They could have dropped simply handing you an appropriately-typed Pokémon for the battle, though.
Late-game, the starter ideally shouldn't surpass the other options you've got, at least not by a huge margin. The starter should pull its weight, indeed, but it shouldn't be the best Pokémon available. Other Pokémon should be able to do some jobs better than the starter, at least in some circumstances. The starter should not be outclassed, though, nor should it be relegated to some niche. At least not by design. The more roles your starter can potentially fill, the better, as that allows for a huge variety of play styles with the same Pokémon. This is where balancing starts to become difficult. The starter shouldn't be able to fille every role at the same time, since that would make it overpowered (as in, make every other Pokémon look poor by comparison). It shouldn't put too much focus on defenses, because that means its offenses become too poor for it to crush opponents (which is important for Exp.). Likewise, too high offenses, and it won't be able to take hits (and a Pokémon that warrants a return to the Poké Center after every battle, is not very fun to use). Too low Speed, and it will take a hit in every other battle, necessitating frequent recovery. And of course, the movepool should be quite wide, but not to the point where it's hard to pick moves for it (a legitimate concern for the less experienced players, which comprise a very large percentage of the player base). However, coverage is a must, lest the Pokémon stops being fun (hi, Serperior!).
All this means that it's quite easy to make mistakes when designing starter Pokémon. Make them too powerful, and the play experience centralizes around the starter. Make them too weak, and the players will stop using them in favour of something better. And everything must be seen in relation to the challenges the starter will face, that is, the layout of the game. A Fire starter can be very good, but underwhelming if the game throws Ground and Water Pokémon at you around every turn. A Grass starter would have the reverse problem. Of course, all three starters will have to match the requirements of the game (or, well, vice versa), and they're all restricted in terms of typing, at least for the first third of the game. Grass/Fire/Water is pretty much a requirement because of how intuitively they illustrate the concept of elemental types to new players.
And last, the starters shouldn't be bland either. They should stand out on their own and be recognisable, as they will feature pretty heavily in marketing. Initially, Infernape had some problems with this, seeing as it had the same typing as Blaziken. There are seventeen ways to make a dual-type Fire Pokémon, but they managed to use the same combo twice. That kind of took away the point of using a dual type for variety. Then Emboar came along and repeated the trick
again, and the blandness factor shot through the roof. Meanwhile, Samurott's design was a little poorly received (bipedal blade-wielding otter -> Mustachioed sea lion? What?) and Serperior had underwhelming stats and movepool, making the Gen. V starter trio the worst ever, in the eyes of many (though arguments can be made that as the generations progress, not all of the previous ones are as fun to use any more either - there's not much standing out about the Johto starters nowadays, is there?).
Hidden Abilities and Mega Evolutions are a nice touch, though, as those allow the starter to break the bonds of the frame they have to fit into for story purposes. A Mega can be totally focused towards one stat, or have stats far exceeding what would be "healthy" for story progression, because Megas have healthy competition for that team slot (and they're mostly all overpowered anyway). Hidden Abilities could send the Pokémon into a niche that would make it way too one-sided for a story playthrough, but give it awesome competitive presence. As long as the HA or Mega Stone aren't available too early in the adventure, the designers can be very creative here, transforming an otherwise rather dull Pokémon into something unique and powerful.