Ohhh I love these kind of threads! I'll do the very first 12 veterans first from Smash 64, then in a next post the Melee veterans because well.. I frankly don't feel too much for writing these out too much.

: Mario is all around a great balanced character, and fine tuned in Smash 4 to have a great combo-based playstyle. YET! There's quit a bit I would see changed. For example, why did Dr.Mario, and not Mario HIMSELF get the famous 'Goomba Stomp' attack? Mario basically invented killing enemies by jumping on them. I also think F.L.U.D.D. was just kept in to differenciate him a little from Dr.Mario's return, which is rather lazy. Does it matter that much that Mario and Dr.Mario have differernt Down B attacks, but Luigi still has the Cyclone....? It makes no sense really. I also liked his Fire Balls best in Smash 64, where they felt most like the fire balls in the Mario games, but slower. I also don't like the Up Smash, it's a rather random move. If Paper Mario yet again doesn't make it, why didn't they give him a overhead hammer swinging attack? That's pretty staple of Mario at this point.

: Yes the original Leader of the Bunch! I'll admit, in the beginning I didn't feel much for Smash 64's DK because he felt so different from the DK I myself grew up with from Donkey Kong Country. It took a while, but with his dash attack changed in 4, they made that one change that was absolutely needed. Besides that, that old dash attack was straight up awkward. Speaking of akwkward, Head But... It's not a good move in design, in utility, and looks rather dumb. Why not make it a sort of double fisted ramming attack somewhat similar to a grounded Forward Aerial that does exactly the same thing??? It would improve the range, and with DK's strenght, actually would make a lot of sense instead of headbutting people into the ground...
I get his design doesn't really allow for a projectile, much like Ganondorf's, so I won't complain about no barrel tossing attack (because given how strong the barrels are in Smash, it'd easily be broken) - but there's a lot what you can do with DK which stays true with his character. He's without a doubt the one Smash character who relies most on raw, brutal strenght moreso even than Bowser and Ganondorf, and they could've gone with a grappling type of attack. It's rather ironic that Diddy got a command grab with Monkey Flip before DK, and it's a great fitting move, whereas DK's Headbut is just ughhh... I also don't quite like how they change up DK's personality so drastically each game. Smash 4 was wayyyy too goofy, and Ulitmate's DK looks way too aggresive; I hugely prefer the Brawl DK look, as it also looks most like Rare's Donkey Kong. Also strange they managed to avoid the DK designs of Returns and Tropical Freeze, which where also AAA+ designs.

: The Breath of the Wild redo of his moveset really makes him feel fresh! This is a Link I really look forward to playing as. The only thing that doesn't really fit is his Boomerang, but I'll let that pass because of how iconic it is, and it also sort of feels good to have it back despite not being in Breath of the Wild. They even gave him a regular grab, and sword beam projectiles! This is how you revamp a OG Veteran, Sakurai.

: What hasn't been said already? Ever since Smash 4's inclusion of Mii Gunner, and more noticably Mega Man, Samus's moveset felt.. lacking. It's ironic since at THAT EXACT given point, Samus was given a lot of Melee based attacks in mainstream Metroid games. Other M was the very first to do it, and it came back in full 2D Metroid with Samus Returns 3DS. And Samus has also finally been given the ability to charge her beam in midair... Still, Power Suit Samus feels rather lackluster overall. She needs to be a killer machine who rapidly shoots projectiles, and that needs to show in Smash as well. I wouldn't care if the Missiles only did about 5~6% damage max, she just needs to be able to fire them rapidly and instantly and with the ability to aim them slightly. Mega Man and Simon Belmont come from games that are rather similar in design as Metroid, why do their moveset reflect that extra polish more than Samus's?? It's also sad they stuck with the Other M Samus design BUT INCLUDED
TWO METROID NEWCOMERS with vastly different designs..... I predict a 3rd time Bottom Tier yet again, sorry. This character just won't get no love.

: I think Egg Throw has been redeemed. Finally. But now what else sticks out? His tongue certainly doesn't... It needs to be at least twice as long. And give him a semi-grappler related playstyle. Why is he not able to eat stuff with his Neutral B while Kirby and even Wario can? Other than that, I think Yoshi is actually a rock solid character in terms of representation.

: That Inhale buff was literally all that was truly needed to fix Kirby up. He's already insanely light, and has bad recovery to boot despite the 5 jumps. So being able to spit back projectiles and healing by inhaling them is great! It was the ONE change I wanted for Kirby, and we got it. There's just way too much to include for Kirby, possibilities for a moveset are endless. I like how Burning is back as a Dash Attack as well. Final Cutter is kind of underwhelming however. It's just very weird overall how Kirby wasn't given the ability to eat stuff up with Inhale and heal with it, but WARIO was...

: What else can we expect from a character that's 99% of the time airbone and his franchise is bound to recreate that one N64 game for the rest of eternity? *sigh* Fox's moveset is good creative liberty, especially within StarFox canon. The Reflector is genious, so is the Blaster and the others wellllll... They fit? Side B looks convincing enough, and heard a few bit of inspiration for Fox's moveset even came from the Kitsune legend in Japan, a apperant fox mythical creature of great strenght. So that's kinda cool.

: Skull Bash is kind of an eyesore. Why didn't they change it up for Volt Tackle whenever they could and use Catastropika as a new Final Smash? In general, Pikachu needed farrrr more electical attacks in his moveset, and now moves as N Air are changed, and he gets electrical effects on attacks like F Tilt and such. They could do well with changing up Pikachu a little bit, but like Fox, he was always a character that had a very solid kit and consistantly was placed as at least High Tier. A worse overall representation than say, Mario I would say, but still sort of acceptable. They should play around with his moveset a little, for example making the Thunder Jolt a chargable projectile attack or something? Or make it Thunder Wave, with a similar animation but a lottttt of hitstun. Down Smash can also be changed up to say.. a electrical shockwave attack that comes from the ground or so? Use his tail more in aerials, as say, B Air? I also think he's too big and if he gets revamped, make him lighter, stronger, and have way more ranged attacks. He should be around Kirby's current height but be a small character with considerable range, power and hitstun.

: So, he's walking around in that Castlevania castle with his Poltergeist, which is arguably wayyy more iconic to Luigi than F.L.U.D.D. is to Mario, yet he only uses it for his Final Smash? Then why was it so underwhelming in that trailer? It's just weird. Yeah I don't expect him to change up all that much, and I wouldn't mind. Luigi is okay as he is I feel.

: As a Ness enthusiast, am actually glad they decided to change up that headbut U Air. He got way more PSI-related attacks ever since Smash 4, and Brawl did a lot to flair them up as well. He hasn't used his own PSI ever since Smash 64, but I don't care about that at this point. Ness is cool, he uses offensive PSI, a PSI barrier attack, his bat and his yo-yo. So he's overall really well done. I personally would change his Forward Tilt and Dash Attack to bat attacks as well honestly as to give him more disjointed attacks, but hey, can't complain.

: Even IF a new F-Zero game came out and gave this guy lots of canon material to work with, I wouldn't want his Smash moveset changed ever. Legendary status at this point, and top peak of creative liberty mixed with randomness. He represents Smash more than his home franchise, and the overall wacky, weird and random nature of the game. C.Falcon is golden, don't touch.

: Nothing of noticable worth to discuss here. She never jumped like she did in Smash in Pokemon games I recall. But who cares? Her base moveset and Specials represent her actual abilities in Pokemon better than even Pikachu's. Pound, Sing and Rest are quite iconic, even if she doesn't actually learn Rest, it fits her theme. Roll Out is random, but a cool random one, like Mewtwo's Shadow Ball. Probably added to Melee because they needed some Generation 2 GSC moves in there. If I would change a thing, I would make Sing a more ranged attack. That one of the musical notes just drifts off after Sing has been used, and can cause sleep status from a distance when it hits. Pretty useless move overall honestly, despite it being her MOST iconic move ever.