Okay, I'm looking for the best characters out there... the cream of the crop. Those that will act as if they were always meant to be in Brawl the whole time. What ones are those?
Ideally, I'd like to add Mewtwo if he's any good, and same for Roy, but I won't if either of them are jank in any way.
These will also be for vanilla Brawl, so keep that in mind. Tripping sucks, but it's just part of the game, and I've gotten over it.
I can only go off my own experiences so bare that in mind. For completely new, different and working (i.e I haven't encountered any issues):
-2D Marisa over Lucas - Inawordyes mentioned this one, and I'm a Touhou fan so that obviously helps, but this is my favorite PSA. Fun and versatile moveset, brilliant visuals, not OP but not weak, tons of Easter eggs, it's just a blast! Has some cool alts including recolors and other Touhou characters.
-Scott Pilgrim over Lucas - Inawordyes mentioned this one too, great moveset and if you're familiar with the character you'll really appreciate this one
-Geno over ROB
-Goku over Pit
-Cloud over Ike (I use the Cloud Strife Fusion Blader one personally, which is the newest Cloud PSA from memory)
-Sephiroth over Marth (The 5.2 version works well from my experience)
-Majin Vegeta over Pikachu
-Villager over Pit
-Megaman over Snake (based off of Smash 4's model)
-Skull Kid over Toon Link (Slightly OP maybe, haven't decided yet)
-Zero over Link
-X over ROB
For New characters that may have some minor issues or not feel 'Perfect':
-Viewtiful Joe over Captain Falcon (Really fast, may feel odd but really well done)
-Future Trunks over Ike (Works great EXCEPT never use the Side Taunt while facing Left or it will crash for some reason, but otherwise it's perfect)
-2D Alice over Mario (Brilliant PSA that's similar in nature to the 2D Marisa, but Insanely OP and can be unkillable so only use for fun or if you don't care about God PSA's)
-Roll over Zelda (Down Special is the same as neutral special due to nature of no transforming, some small hitboxes with some jab and tilt moves but I find her comfortable to use and she holds her own)
-Lloyd Irving over Wolf (Set is fun, especially if you love Tales of Symphonia, and works fine, but I find the voice effects annoying unless you're using the included SFX file. Just my opinion, so otherwise it's perfect)
--Lucina over Marth (Actually plays different to Marth, fun moveset)
Movesets that are great but similar in nature to other characters:
-Battletoads over Ganon (A combo of Ganon and DK's moves with one or two twists. Plays well)
-Roy over Marth (There's a few out there depending on your preference. I like the Hybrid one myself)
-Saber over Link (Similar moves to Link with some twists)
-Aryll over Link (See above)
-Skyward Sword Link over Link (Alternative take on Link's moveset based off SS)
-Momiji over Link (See above, but resembles Skyward Sword Link)
-Young Link over Link (Similar to Melee Young Link with some twists)
-Gray Fox over Meta Knight (Bigger then Meta Knight with some differences but similar in the sense that he thrives on quick movements and dominating slashing)
-Broly over Ganondorf (Some alternative moves but feels similar to Ganon with some similar moves)
PSA's I haven't tried but look quality:
-Shadow over Sonic (Not sure of best version)
-Mewtwo over Lucario (Not sure of best version)
-Dry Bones over Lucario
-Koopa Trooper over Jigglypuff
-Gotenks over Lucas
-Neku over Lucas
-Deadpool over Snake
-Windwaker Toon Link over Toon Link
-Knuckles over ? (Not sure of best version - Jigglypuff?)
-Tails over ? (Not sure of best version - Jigglypuff?)
-Majin Buu over Lucario
-Kid Buu over Lucario
There's probably a lot more great ones out there but these are the ones I've tried out and enjoyed, or ones that look really interesting and quality based off previews and moveset info. Hope this helps a little