well it depends...
Captain Falcon, Peach, Roy, Marth, Ike (possiby) and Fox (as far as I can tell) speak in full sentences, and we have accepted this. so they are more likley to have a lengthier speech pattern within the game
Mario and other characters tend to speak in short, quirky phrases such as "Lets-a-go!" and we've grown to accept this. however, we have never really heard them say a full sentence
Link and a majority of other characters are the strong silent types, usually only using grunts and yells. I guess that almost nobody would want Link to speak, as it may take away from the heroic illusion that we have grown accustomed to.
Sonic, I think, would do fine in any of the categories. the last two would be ok and he wouldn't need to be changed. The first one, however, could do with him getting a better voice actor. his age, canon wise, is 15, so he still has a wide range of people who could do a better voice over