Personally, the right balance would be having 'x' character only paths, but being able to access most of them with other characters if the player has enough ability or by using a not so obvious way. For example:
Sonic´s emblem on GFZ1 in SRB2 (most players wouldn´t have even tried to reach the house with Sonic if it wasn´t because that emblem):
http://www.youtube.com/watch?v=Ku_dWyraQNE
Reaching Carnival Night boss with Knuckles in S3&K:
http://www.youtube.com/watch?v=D2tPUcG3bKk
I mean: Yeah, there should be paths made specially for Sonic, Tails or Knuckles. Being able to access them with other characters doing something not so obvious is cool though.
About Sonic only paths: They can be done either by high speed (ERZ2 already did it if I´m not mistaken), or having some kind of trap that could only be passed with a thok. Again, you could make these kind of paths accessible by having a speed box either hard to find or timed far away, requiring playing too good to reach the path with Tails or Knuckles with them on.
Anyway, I think that was the original idea in SRB2 to begin with, and that´s how S3K actually plays on many parts. One of the fun parts about that game when I was young was trying to get into a path where I shouldn´t be.