Actually, contrary to popular belief, they say Mewtwo and Roy were kicked because of time constraints, not Lucario and Ike. I halve-ly believe the Roy part. Mewtwo apparently was also planned for ssb64(I heard) but was scrapped due to limitations. Idk if I should believe this, as they are starting to say this for Bowser and DDD too (even if he appeared on the bg and he's Sakurai's).
Plusle and Minun were supposed to be the new Pichus (replacing the only melee character missing), but they were scrapped.
Dixie was supposed to be paired up with Diddy, but cut due to difficulties.
Dr. Mario is vague and technically unknown, it's speculated he was used as reference (from data imported from Melee or something), or an alternative costume, or maybe both?
I have no idea for Toon Zelda/Sheik.
Also apparently, for ssb4, Skull Kid won against Megaman for 2000 votes (Both had 38%) in the North American (And Europe) poll. Skull Kid isn't a bad idea, specially since i can't think of another Zelda character that I recall that might fit and be original, though Megaman would totally be better, as it's a mascot, and Sakurai is limiting characters, so another Zelda rep might be hard on this time of development over others, I think I heard Megaman was going up in votes when the poll ended, so he might've won, might just be an excuse to try and get Megaman to win though. Also everyone was fine with Capcom being in, the Street Fighter guy preferred Megaman over any of his characters (And Bison over Ryu), Capcom USA was fine with it, and Capcom Japan didn't have any objections (from what I heard).
And apart from that, yeah, I never knew about the playstation one and I never got why Snake hated Sonic, if it wasn't just 4 teh lulz. Some just blue screen'd my mind.