Characters I think need to be included would be someone new from the Metroid Series as their own separate, playable character (a smaller version of Ripley, anyone?) and another playable character from the F-Zero series.
Why? Samus and Captain Falcon are the only characters in the first Super Smash Bros. that have not had any other characters from their series appear as a playable character in Melee or Brawl.
Now, I'm a massive F-Zero Nut, and I have some characters I would suggest as being added, in order, but it's long, and to save space... And, I would argue that only one would deserve the spot. I ordered them in what I believe most likely, not my favorite.
1: Samurai Goroh: No big surprise that he is number 1 on this list. He was one of the original four characters in the first F-Zero game, and from the start has been depicted as Captain Falcon's main rival. He also has been an assist trophy already. So, there is some Smash history associated with him. His combat would be interesting also: In both the F-Zero and Super Smash Bros. games, he has been shown to be able to swing his sword at very fast speeds. However, he would most likely be a heavyweight character. True, there are already a lot of swordfighters in game, but how many speedy heavyweights are there? Quick attacks that rack up damage quick while being hard to kill... If he even had 1 decent finishing move, he would be a great addition and a true force to be reckoned with. But don't expect good recovery skills. His final smash could be similar to Captain Falcon's as vehicle based, but I would find it more interesting to see him drive the length of the course, spinning wildly, with the ability to hit all opponents on screen, just not an insta-kill, like C. Falcon's.
2: Black Shadow He hasn't appeared in as many games as Goroh, but after F-Zero X, he has really overtaken his spot as C. Falcon's rival. In fact, in F-Zero GX, we even saw that Goroh isn't much of a threat anymore; it's Black Shadow. A powerful mad mind, ruler of the underworld, in both game and anime. His inclusion would honestly make just as much sense as Goroh's; the only reason I view Goroh as more likely is the character's longer history. In game, he towers over people and is slow moving. He also has the heaviest ship in game. He should play as a heavy weight brawler, slow and strong, high resistance, quick falling with slow but powerful attacks; in the vein of Gandondorf, Bowser, etc. Final smash? How about he binds 1 person unable to move if they get to close and then plants a bomb on them, similar to how he captured C. Falcon in F-Zero GX story mode? The explosion would deal high knockback/damage to the person binded, but also to anyone that gets too close... On that note, allow the binded person to be treated like an item, throw them around, and give a random amount of time, say 5-10, before they blow. A timer would be displayed on screen.
3: Pico: A violent assassin who isn't really good or evil, just crazy. Like C. Falcon and Goroh, he was one of the original four characters in the first F-Zero game (the last character was Dr. Stewart, a mostly pacifist doctor, who really wouldn't fit in a fighting game). This green skinned alien is cold hearted, a master hitman of the Poripoto army and calls the planet Death Wind his home. Reasons he would work well: he looks unlike any other character so far in the Sper Smash Bros series, from his red eyes, to green skin, lumbering stance, fangs and a large shell covering his back. In F-Zero GX, Pico was shown in a short video to be highly acrobatic and fast... and an expert marksman. Utilizing multiple guns and lasers, Pico could be played as a speedy, ranged atttacker with mid level to high recovery skills. Even when he would launch melee attacks, he could bash people up close with his array of guns. I would say his final smash should be similar to Solid Snake: you get a little bit of target practice. But his shot fire quicker, are more accurate, with less damage and knock back dealt.
4: Deathborn An immortal creature and lord of the underworld, with his first appearance in F-Zero GX. He even makes the mighty Black Shadow cower in fear. He is ruthless, pure evil. He enjoys forcing people to attempt to complete impossible tasks and then banish their lifeless bodies to drift in space forever for their failure. Why would he be awesome to play as? In game, he never really fights face to face. He uses his ability to teleport, warp time and warp people to complete his bidding. If he could use such attacks in game, it would be unique. His recovery moves be teleportions, he would have the ability to bring enemies closer or farther to him at will (this move would not damage them) He could bring someone close, do a few melee attacks, and warp them away before you have a chance to react. Pretty cool idea I think. It would be hard to make such character balanced, however. His final smash: He sends out a beam of light straight forward, and whomever it hits is intsa killed. They get teleported away. You don't even see them get knocked off screen. They just disappear and lose a life.
Over all, I think Pico would be the coolest, but I would say Samurai Goroh has the best chance. Thanks for reading the really long post relating Smash Bros and my favorite game series ever, F-Zero.