how... would that work?
Have Act (level) size determined by size ranges (for example, 7-12 screen-lengths tall by 20-25 screen-lengths long), broken into discrete sections of 128x128 level element blocks. Each standard 128^2 block will contain raw (no-object) level segments, which will be fitted by a pathfinder to generate (1-3?) level paths.
The level will then be populated by a variable number of enemies, rings will be added in terms of clusters, and then level objects (tubes, springs, corkscrew paths, Z-bend tunnels, see-saws, crushers, spikes, floating/moving platforms, and such) will be added based on the level theme.
Boss levels will have specific areas of the level board pregenerated (Eggmobile + room as a setpiece), Chaos Emerald Portals (Giant Rings!) will be pregenerated inside a specific type of "room" block, and hidden tunnels will be dug through a level. The other important pregenerated level block is the Level End block, which either has a Prison Egg capsule (gives points or rings) or a Level End Marker (may give items).
Special Stages could be either pregenerated or randomised, using similar principles depending on the type of Special Stage implemented.
Of course, being forced to navigate a Zone made mostly of springs, zip tubes. bottomless pits, and spikes with few rings won't be very fun, so population limitations/modifiers may be used to adjust the difficulty of the zones. For added player effect on the game, make it so they player can influence the level generator by fulfiling specific goals in-game (Sonic CD style Badnik maker destroyed = fewer enemy spawns, for example).
As a full example, a level generation set for random Green Hill:
Level Theme: Green Hill (This defines what objects and enemys used to populate)
Zone Size: 25-32 long by 5-9 tall
Zone Length: 3 (Determines number of acts generated for the zone, boss level is generated for the last Act of zone)
Ring population: High (180-200+; This determines number of Ring Clusters used)
Enemy population: Low (15-24; determines how many enemies placed within the level)
Trap population: Medium (25-40)
Level Object Density: Medium (3-6; determines how many objects to spawn per 128^ level block on average)
End Level Object: 75 marker/25 capsule (percentage chance of getting either the Egg Capsule or the End Marker at the end of level.)
Getting the game to generate "Speed" or "Platforming" levels could be tricky though, unless the generation formula for pathfinding is different for both.
