Sakurai has been quoted as saying that we can expect 'a more robust single-player game' in Brawl. There was an attempt at this in the Melee too, so I guess it's an even further expansion of what we saw there. But how can we get more out of playing alone?
One of the neater single player mode ideas in the last game was the Adventure Mode, which blended sidescrolling gameplay with the normal combat. It's pretty nifty, although playing through it with every character was a pain.
Another great mode from Melee was the Event Battle, which put specific rules and goals for each match. It was challenging, creative, and fun; easily one of the highlights of the entire game. Most people would appreciate this coming back.
One great way I can see the return of both while expanding on their ideas would be combining them into a single, slightly longer mode. Fusing the specific goals of the Event Modes with a sprinkling of sidescrolling levels would make a mode that has length, challenge, and variety. There's much more to this than that, though.
My main inspiration for this mode came from two Smash Bros.-like DS games: Jump Super Stars and Jump Ultimate Stars, both published by Nintendo as well. In these, the single-player mode has a large overworld (think of games like Super Mario World), with each level having a number of objectives that you could complete to unlock stuff. Sometimes, by completing certain goals, you'd unlock new paths. Even after beating the supposed final boss (twice!), there were still levels to explore. All in all, it was a good way to entertain yourself all by your lonesome.
Seeing this idea incorporated into Brawl would definitely be a plus. You could base all the overworld maps on all the different games represented, have each level come with a main objects plus a couple of side challenges. By completing these, you could find more paths to take (and maybe allow some levels to incorporate secrets from later in the game.) Like the Event Mode, you could save your progress so there's no worry like the original Adventure Mode. Also, you should be able to switch your character on the fly, so you don't have to play through it with each individual character (which would get tiresome). There's also be plenty of opportunity to insert unlockables.