Brawl has tons of good stages; a lot of players just started having unreasonable standards for stages. Lylat Cruise and Pokemon Stadium 1 are obviously fair game for starters which puts you on par with melee's generally accepted list. Honestly, what's unfair about the Halberd at all? Braindead people might have trouble with the hazards, and you have a small amount of play around them which really doesn't favor anyone very much anyway and is an aspect of the game that's probably good to have represented in the starter stages (if they are supposed to represent the most fair selections from the game as a whole, why completely exclude major aspects of the game such as damaging hazards or stage movement?). With stage striking removing it as a factor in the small number of matchups (less than 1% of the total matchups in brawl) where the relatively large presence of walls and walk-offs can get dumb, Delfino Plaza is obviously a very fair stage that works as a starter. PictoChat even is very fair if you play smart and are dynamic; the only real problem with it being a starter is that most players aren't very flexible and are really bad at adapting to changing conditions (and quite a few play like total morons on certain forms by jumping into damaging hazards and doing other such ridiculous things; I'll never understand them). If you really want diverse starters, brawl offers it. Just use what the game gives you.
I'm sure I'm going to get flack for this, but melee's starter list is really boring. Fountain of Dreams, Battlefield, Yoshi's Story, and Dreamland 64 all follow the same archtype of "three platforms with the middle one more elevated". They change a few proportions and have generally different sizes, and they each have their own minor gimmick (the cloud + Ness hating Shy Guys, the wind, the movement of the lower platforms, and the edges you can't slide up to grab the ledges). Still though, they're pretty homogeneous. Then you have Final Destination which is a flat line (deceptively unfair in general, by the way) and Pokemon Stadium 1 which is the only stage on the traditional list that incorporates dealing with fundamentally different platform layouts than "none" and "basic 3 platform" and had transformation and walls and tons of other features that definitely make it unique and interesting.
Really, melee's starter stages are 6 stages with 3 ideas (though adding DK64 would increase each number by 1); with brawl, every candidate for a starter has its own ideas, and more of the total game can be contained within them. Pass through floors, water, damaging hazards, moving platforms, various schemes of stage transformation, walk-offs, sloped ground, stages you can and can't navigate under, various stage side shapes that have big impacts on games (Lylat and Pokemon Stadium 1's easy to attack through ledges versus the flat walls of Yoshi's Island [Brawl] that are great for wall jumps and wall clings)... A lot of people like to call these things "problems", but they're important parts of the game that, when they are not in such an excess as to create great unfairness, add depth and diversity to the game. Even in just those starters, brawl contains "the whole game", and in each individual starter stage that implements these features (or doesn't!), you have a very unique idea for a stage relative to the other stages on your list. If you have 9 starters, you have 9 unique stage ideas. I know that every starter stage in melee gave assorted actual advantages (save your strawmans for another day), but the shared core concepts are just plain less interesting in the long run and limit the game in its ability to represent more of the game in the starter stages.
Of course there are quality stages from the previous smash games that would have been nice; Poke Floats was a really cool and interesting stage, and even among the more boring stages that so many of you love, I can't say I could disagree with "more is better". I suspect that importing stages directly was not an option with the new physics engine, and you can tell that the old melee stages were rebuilt in brawl's engine as opposed to just ported. They evidently decided that they only had enough development effort for 10 returning stages, and I can understand why they made the choices they did. Brawl's overall stage list is easily the best in the series if you actually like stages; I just don't see why people feel the need to complain about it. The presence of awful stages is unfortunate, but it's not like it's unpredictable, and they did a really good job of making most stages actually playable if you actually want to play on a bunch of stages. The even better part is that most of the actually bad stages are stages that they obviously didn't try very hard or at all to make fair (Mario Bros., etc.). A few basically good stage designs implemented wrong are depressing for me (Summit, Flat Zone 2, WarioWare), but I can't say I have sour grapes over New Pork City or anything...
Also, people other than me like Fourside? Fourside is cool because it's EarthBound and I kinda like camping, but I thought most people really hated it.