I really hate being the first to post, but I do suppose it's a nice thing.
Going by the new stage selection, I see that Pirate Ship is still a legal stage. Of course with the natural hazards and transformations of the stage, I could see Toon Link getting an even more solid advantage over Sonic. I assume you guys are trained to work with projectiles on non-flat stages and Sonic has no where to run except to another side. I would suggest either stay in the middle or if you somehow get Sonic to go into the water go for it.
Assuming that's not available to you (maybe the other player banned it or you live in a ban-happy area), I would like to know how Norfair works. Toon Link has a d*** fine aerial game AFAIK, and since most of this stage is (lol camping sucks but it counts), what could go wrong? Sonic's aerial game is horrible compared to his ground game, so that's a detriment.
...If that's not available either, then what about Final Destination or Battlefield? You don't want to go to Yoshi's Isle since Shy Guys would get in the way, and Sonic gets iSDR here.
If possible, how willing are you going to go to Weegee's? Not the best idea but I'm just throwing it out there.
Maybe not so much Lylat, since it kind of tilts and screws around with peoples' range game/recovery whereas Sonic can easily take the shifting...
You might also want to think about Picto since Sonic can also gain iSDR there, but it might not be so problematic as YI:B.
I don't really like/think too much about any of the MAY-LAY! stages, so you're on your own there.
Toon Link has that certain advantage to him that allows a wide variety of stages to choose from, nothing immediate comes to my mind in terms of what stages Toon Link wants to stay away from unless you count YI. Sonic on the other hand has that same freedom, but to a lesser degree since his opponent can do just as fine on a stage, if not better. As if a solid 4:6 disadvantage wasn't enough to deal with, just the playstyle of getting around those projectiles... but I digress.
Please take my advice with a grain of salt, I happen to think it might be personal preference more than something like "Olimar's Mansion."