The easiest answer is to stick to 2D. To make this question more interesting, I'm going to assume it has to be 3D.
Make characters relative similar. All can run fast, jump well and homing attack. Some characters can do some of those things better or worse than others, but all can perform these tasks well enough. Then you can add other abilities for some characters such flying for Tails, gliding and climbing for Knuckles and eardrum shattering voice for Cream.
Stages should promote fast and fluid movement. Try to stick to what the player can do while controlling the character and avoid long sections where the player is expected to let the game play for itself (spring and loop sections.) Finally, the player shouldn't be forces to stop and fight a bunch of enemies in order to proceed. Even if the player chooses to do so, enemies that takes more than one hit should be an exception.
Keep the story simple. We don't need a triple viewpoint time traveling story and we don't need any lessons about humanity in a sonic game. If Sega don't want to take the same route as Nintendo did with Mario games and make story near nonexistent, then I suggest they focus on characterization.
