At this point I would prefer a fan remake using the Retro SDK than anything official. The more official you make it, the more it will likely stick to the original's blueprint. Give me the option to play the levels sequently and in order, ending with boss before proceeding to the next, but still giving the player an Origins like classic mode to have the random selector. Same with the combi-catcher. Then it is what most others have said. Adjust the level layout to not be overly samey, add objects and badniks to the levels, and find a way to evolve the gimmicks already present. The lights in Amazing Arena being a prime example. Maybe I'm just insane, but the mention of adding metroidvania elements to the game has got me thinking. What if the character capsules were rewards for beating each boss, in a similar manner to Sonic Advance 3. You start the game with Knuckles, who has gone looking for Sonic and Tails, and comes across Espio. Then you have bomb and heavy as options in the catcher, with empty spots for those not unlocked. Then as you play, you unlock Mighty, Vector, Charmy, Tails and Sonic as you play across the 5 zones. Maybe even throw Ray and Amy in as bonus characters in random zones like they were the Black and White Yoshi's from Yoshi's Story?