I feel like doing a Sonic heroes type thing mixed in with Sonic Adventure 2 style. Having Knuckles with his Chaotix, Shadow with Rouge and Omega in Gun, and Sonic with Tails and Amy all having their own story-lines that intertwine every now and again, and then (as expected) come together for a final story and battle Eggman or whatever the diabolical villain is. Each story can have different play styles and stage types to match how they would interact with one another, like Shadow and Sonics stories would pretty much be like Sonic heroes in terms of switching between characters to get through certain areas, and then Knuckles Chaotix group could be a choose 2 to go through the level so that players can always have their favorites, yet some levels have certain things you need certain characters to complete to add replayability, such as needing Knuckles and mighty as a pair to break down a wall to a secret area, or Espio to sneak through somewhere and what not. I say through in 10 levels for each story for a total of 30, maybe 3-6 for final act so that each group has a stage + the final battle. Sorry if this seems little over-specific, but it just came to me as I typed it.