I say Toxicroak, not only because it's one of my favorite Pokemon, but it would make a lot of sense being in SSB.
It's fighting style is different than the current Pokemon in SSB, so it wouldn't be a clone, and it has access to a good moveset that could fit well into. Not only that, but it being one of Brock's Pokemon in the anime should mean it has enough fame for people to know who it is(I don't watch the anime but I think I remember seeing him with one, anyway).
It's moveset could be:
Neutral B - Poison Jab: A quick attack that does small amounts of damage, and does a stacking 1% damage per second poison that lasts for 5 seconds, caps at three stacks (basically does a base damage then adds an additional 15% damage if they escape).
Forward B - Pursuit: An attack that does a short dash and a moderate amount of damage if hitting the target from the front, but double damage if hitting the opponents back. (the dash would be a shorter distance than most SSB dashes, and the frontal attack would do comparably less damage than most other forward B's, but the one from behind would do more.)
Down B - Swagger: This is less of an attack and more of a utility type skill. What it would do, is last about 2 seconds, and reverse the other players controls, while increasing their damage output by 1.5 times its normal amount (which wears off immediately after the swagger stops). The key to using it properly would be as a surprise, so you can trip them up and get a couple seconds of free attacks, however if they catch on fast enough, they can turn it against you for a bit of extra damage.
Up B - This one I'm having a hard time figuring out. Obviously not because of lack of attack ideas, but rather lack of ideas of finding one tied to a recovery. Out of Toxicroaks natural movepool, I suppose you could use Mud/Sludge Bomb, and have the explosion boost you up, but I feel like that's too much like Yoshi. However if they don't mind using move tutor attacks/TMs/egg moves then you could probably use something like Bounce to easily make up for it. --- You can never be too rich, too good-looking, or too well armed. Pokemon White 2: 4986 2948 4576
I'd say Zoroark. With his Illusion ability, he'd probably be sort of like Shang Tsung in the old 2D Mortal Kombat games, and be able to turn into anyone else. That could be fun. --- "There's a whole lot of Internet porn out there. It's not gonna download itself!" - Dr. House