These choices represent outside of the box thinking. They aren't safe; Nintendo would be going into a whole new direction with Super Smash Bros. A more comprehensive and magical direction for the fan-favorite series.
Necrid - Soul Calibur II
Back in 2003, Soul Calibur II graced us with one of the best fighting game characters ever. Visually designed by Spawn creator Todd McFarlane with input from Namco, Necrid left a deep impression on the hearts and minds of Souls players. The character had a unique fighting style that certainly didn't just pull moves from other characters. Imagine Necrid in Super Smash Bros, bringing his unique aesthetic and punishing fighting style to Nintendo's brawler. Best addition ever? I think so.
Mara - Shin Megami Tensei
Some people would choose someone from the Persona cast like Teddy, but they would be wrong. In the long history of the Shin Megami Tensei franchise, there are few characters as iconic as Mara. Some might say, "Mike, that's a penis on a chariot!" but I counter that a penis is exactly what Super Smash Bros needs. What better way for the family-friendly title to reach new heights than by serving as a gateway to the most important conversation a parent can have with their children?
Sorceress - Dragon's Crown
Speaking of having a conversation with your children, the next character that would do well in the world of Super Smash Bros is the Sorceress from Dragon's Crown. George Kamitani's designs look great in 2D, but I think Nintendo could do a great job translating the Sorceress' figure into the 3D space. Sure, Nintendo has closer access to Bayonetta or a Fire Emblem character, but it's better if they go the extra mile.
Pyramid Head - Silent Hill 2
If you're adding Cloud to the ever-growing list of Super Smash Bros' sword-wielding characters, then I have another one for you. Sure, Silent Hill 2's Pyramid Head actually handles the Great Knife, not a sword, but I argue the difference is negligible once a blade goes beyond five feet. Plus, who would dare edgeguard the manifestation of James Sunderland's semi-sexual vengeance?
Alma - F.E.A.R.
You know what Super Smash Bros needs? More characters with the innocence of a child. If you've played any of the F.E.A.R. games, than you probably know about Alma, the misunderstood psychic antagonist of the series. What says "Super Smash Bros" more than a creepy, Ring-like little girl who tears her opponents limb from limb? I'm sure she'd be best friends with Mewtwo.
SHODAN - System Shock
How would Nintendo even make a playable character out of the villain of System Shock and System Shock 2? SHODAN is a digital artificial intelligence that manifests as a giant cybernetic lady face with cables and lights streaming from it. But hey, they made Master Hand work as a playable character, so I'm sure if Sakurai and company put their minds to it, they could come up with something grand.