I would say that I would remove four characters from the roster (Pokemon Trainer, Lucario, Snake and Sonic) and introduce at least 18 new characters to the roster, brining in a total of fifty.
In terms of Mario characters, I would choose Bowser Jr., simply because he would fit well as a villain and we could have the Shadow Mario transformation with Down B. Also we need more villains and females.
Mario Sub-Series, King K. Rool. Nothing needs to be said about him.
Zelda, put Ghirahim because he was a memorable villain and he would be a perfect fit for Smash as he could be fast and deadly with his rapiers.
Metroid-Wise, I am sorry to say, but I want Rundas from Metroid Prime 3 more than Ridley. Why Rundas? Because he was a very memorable character in the Prim trilogy, he could have a good set of moves and there are barely any characters interested with ice.
Kid Icarus, put Magnus and Palutena since both are quite popular in the Kid Icarus series and Palutena could bring in more female characters into the roster.
No Kirby Characters I'm afraid, I think that's about it for the franchise. But below them, I would like to see Issac/Matthew and Shulk in the roster since they are very popular in Nintendo
Star Fox, very simple, put Krystal. Since she would be very unique for the game by using her staff.
Pokemon, I know that Zoroark would be appearing, but the character I want to see is May. Simply because she would fit in as a female and that she could represent Hoenn. Pokemon, very simple: Mudkip, Grovyle and Blaziken.
No more Mother characters since that about it for the series. Fire Emblem wise, put Chrom in since he would be very likely.
For F-Zero, maybe Samurai Goroh, or maybe none since F-Zero has been dead since 2003.
Other or Retro Nintendo series, very simple: Little Mac and Takamaru, since they are very popular nowadays and they could represent West V.S East. I'm not so sure about Dillon, but if he replaces either Olimar or R.O.B, then fine for me.
Finally, Third-Party. Take out both Snake and Sonic since they were requested and put in four new Third-Parties. Travis Touchdown would be perfect since he could replace Snake and bring in a whole new set of moves with Beam Katana and wrestling moves. Second, Lloyd Irving with his popularity and the fact that he is from a Namco game and that Bandai Namco are developin Sm4sh. Lastly, Megaman and Bomberman, since both have has a long history woth Nintendo back in the old days and there was a speculation with a Capcom character being in Sm4sh.
Then again, that's about it.