I think the ease with which we all played Mania, even the first time around, is the same kind of ease with which someone will play, say, one of Spelunky's random levels, after playing a lot of the game, even if this is a brand new layout to them (and, since it's Spelunky, it is). We know what most of the gimmicks do. We know how Sonic interacts with the terrain. We know when the terrain is encouraging us to roll at high speeds through it. In other words, we're familiar enough with the tropes that comprise a "Sonic level", that you could theoretically have a procedurally generated "Sonic level", and we'd probably still be acing it. When I think of really good, really difficult, Sonic levels, I think of the Sonic VR romhack. It's difficult, and the challenge is largely for you to figure out how to nail certain tricks in order to clear each level. Having parts of level design turn into physics platforming puzzles could be a good way to force the player to figure out how to progress, without bloating enemy health or instant death zones.
Theoretically? :v: Mania is definitely easier than any of the other classic games, though, even S3K. Part of this is that the game plays itself when you hold down, but it seems to just have less danger overall. Then again, S3K is considerably easier than S1/2 too, in no small part due to the save system (that Mania shares).
Late to the discussion with this one, but enemies with multiple hitpoints would be a strict no-go; the enemies serve multiple purposes. The first is to provide a small obstacle to surpass, and in that case multiple hits make sense (see: Mega Man enemies). However, with momentum-based gameplay such as in the Sonic games, they also function as something to bounce off of to control your momentum. By adding multi-hit enemies, you're slowing the momentum to a crawl (see: Sonic Heroes for an extreme example of this).
