A boost move of some sort or some super accelerator dash attack (like Wario's shoulder bash in Project M) would be a great side B.
Link and Zelda were always mediocre, so there wasn't anything lost in the process.
Japanese Smash 64 Link was average (well, that counts as mediocre), and Link in Melee was only slightly below average. But, regardless, at least in those games, Link was fun. NTSC/PAL Smash 64 Link and Brawl Link, however, were terrible (although NTSC/PAL Smash 64 Link was at least fun). So many terrible decisions made them awful...
Sonic however felt like he had the potential, but felt like he was missing certain characteristics. From experience, Sonic is effective at approaches due to the high dash speed and spin dash combo capabilites, and also an effective edge game. He just lacked the power to be more effective at making kills, which is especially notable with heavy characters like Snake.
Sonic basically had 3 different attacks used in different ways for the majority of his moveset. His moves weren't fast, strong, or high in priority. In other words, his offense sucks. On top of that, his ground momentum never carried over to the air, and, quite frankly, he felt too slow for a speed demon (he should be 33%-50% faster IMO), and his recovery was rather weak considering his previously mentioned big time weaknesses.
In a future smash bros game, Sonic should be a combo demon with more speed, more lightning fast moves, and a hefty amount of changes. The same goes with Link (although only a small amount of move changes should come for Link).