The SE did leave something to be desired. It was a little too straightforward; not too much room to explore. Nevertheless, it was pretty awesome regardless.
1. What about redoing characters/new ones?
Personally, I think Mario definitely needs an overhaul, and the rest of the series' characters as well (excluding Luigi, who will probably be distinguished by his own LM series soon enough). Also, it needs a new character, and not Dr. Mario. I'd be fun to see Bowser Jr. join the fray, since he's played an awfully large part in the series since Sunshine.
And please, do not yarnize or mechanize Yoshi. PLEASE.
The Zelda series needs an overhaul too, but that can be fixed using SS (but for the love of Tohu, please fix Ganondorf) as a base for Link and Zelda. Toon Link can be fixed using WW HD, and the new character...should be either Ghirahim or Midna. Demise would be pretty boss, but he only appeared at the end of the game (in a humanoid form).
But those are the two big series. All the others: F-Zero, Kirby, Pikmin, etc. are doing pretty good, with not much to be desired. Of course, Falcon was royally screwed up in Brawl, so I'm hoping the graphics are better, but his performance is that of Melee. Meta Knight was excellent in Brawl, and I wouldn't change him a bit. And Olimar...I personally hate his fighting style, but he is one of Nintendo's top franchises, so...we'll keep him. Sonic needs more characters, but it was cool to see his start in Brawl.
Nintendo needs more though. I am not saying "add every single video game character ever made" or "150 FTW", but bring some different characters to the spotlight: Pac-Man, Crash, Mega Man, Chibi-Robo, etc. would be good. However, let's not stray from Nintendo too much...
2. Who should go?
This...is where I destroy characters. Let's start with one that for some reason, managed to stick around for all games thus far...JIGGLYPUFF.
Now, many will disagree with this, but in the beginning, he wasn't so bad, at 8 on the tier list. The series had only begun, so it didn't look so bad. But then he appeared again...and things looked even better: 3. To be honest, I wonder how on earth he did that good, because I hated him. And then, he took a nosedive, straight into the Bazaar of Skyloft. 35, out of 38 characters total. Now believe me, I am not basing this on tier lists. I've played as Jigg quite afew times, and have facepalmed and regretted doing it. Yes, he's awfully popular, but he sucks, and he must go.
Also from Pokemon...that dreadful, nameless TRAINER.
Ranking at 28 on the Brawl tier list, this guy is in the Worst 10. Why? I think he leaves a lot to be desired. First of all, the characters seem lackluster (in gameplay though. Who doesn't like Squirtle?) Squirtle=Bowser, Ivysaur I just don't like, and Charizard has the power of his Poke Ball form. Now, I can clearly see Sakurai was trying to offer a new experience, but it didn't work out, really. Add on to that that the Trainer was nameless (hello Ash) we have a character that needs to go POOF!
These are the major one. Others I want out are Ice Climbers, and Ike, but I'm too lazy to write about them now.
In short, that is what needs to be fixed. Is good?
~LTT~
Okay, I feel Mario should have Star Spin as an Up B, and Ground Pound as a Down B, and homing Ground Pound as a Down B that cancels your Up B.
Luigi, same Up B and Neutral B, but Down B should be suck, and Side B should be tap for water, charge for fire, and charge all the way for a block of ice.
Bowser Jr./Shadow Mario definitely.
I really don't want Midna or Ghirahim, they were too minor (only one game each?), and I want to see The Hero of Time as a playable Link instead (probably the most notable.) I was thinking of a really complex moveset, he is only Adult Link, Down B is the Song of Time, making him Child Link, and each of Child Link's specials make him put on a different mask (Goron, Zora, and Deku.) Each mask has a unique moveset. It'd be interesting to see how that plays out.
Falcon is underrated. I know a single good Falcon player, and, while I admit he was way better in Melee, this player performs averagely at tournaments (lower level, but Falcon has more potential.)
Remove Jiggs? Jigglypuff was added as a joke character, and it was actually great in Melee (and I feel underrated in Brawl.) The Trainer should be made Ash, and I feel he should have 6 Pokemon (original starters in final forms? Then the newest starters in final forms? IDK, I've never really liked Pokemon.)
Ice Climbers are annoying, but we need complex characters to stay.
If anyone gets changed, it'll be Meta Knight. He'll either be seriously nerfed or straight-up removed, as he was banned from competitive play. And considering competitive play, balance patches would be a great idea in my book.
I love playing as him 
You know, to troll people online. And I needed to use him to beat Classic with 1 Stock on Intense for that stupid notification (really, no trophy?)
Just putting start-up and ending lag on his moves would make him so much more balanced (Down and Up Smashes, Up B, Fair Bair Dair Uair way too fast in Brawl.)
Tabuu was kind of a surprising appearance. But his appearance was great, he's fun to fight against, his battle song is awesome and Off-Wave is really annoying but it's fun to try and avoid it.
Tabuu was so ridiculously easy. In my honest opinion, he is the easiest boss in the game. His attacks were so predictable, only his exploding teleport and Off Waves actually can hit me these days, and even that is pretty rare (yes, I get hit more by Petey Piranha.)