Mewtwo had his perks in Melee. His throws and Fair were godly, and his Smashes were fun. They just tried to balance him by making him floaty and slow, and it ended up being a bit much. Nothing another go around can't fix. Dropping Mewtwo is kind've pointless if the reasoning is "well, he sucked in Melee." Ice Climbers "sucked in Melee," and they came back. What's there to be said about that? So clearly there's another reason Mewtwo was axed if he was.
That being said, Lucario has the best potential for playable Pokemon out of any of 'em. His moves translate well to a Smash moveset, he's fairly significant to the franchise as a popular and well-liked Pokemon, and despite not being legendary he holds his own in-game as a one-off and "you can do ANYTHING with this guy" kind of Pokemon. The thing isn't that fast with its in-game stats, but his offensive stats are pretty cool. And it learns freaking Aura Sphere. So few Pokemon get such an amazing move, and the ones that do are either Togekiss or Legendaries. Even if Lucario isn't a LEGIT legendary, he might as well be.
With all that, I was skimming 2channel last night (posted about it in the Geno thread) and saw that there were quite a few posts hoping that Sakurai dropped Mewtwo. I was, honestly, stunned. But apparently, and I'm not lying, "Pichu is great! Mewtwo is dumb!" was a popular cry over at their boards. Oh those wacky Japanese... >.>
NOTE: 2channel is a Japanese forum that talks about any and everything, including Smash.