I remember reading a document about level design for Super Mario Galaxy 2, which they would try to introduce a game play mechanic in a very easy to learn environment. Reward the player for learning how to play with the new mechanic, and then have the level challenge the players master of this mechanic.
I think I would want to try to make levels like that. Introduce a new enemy or mechanic to the player, and then have the player learn what to do, and then have the player master it. It would take awhile to think about your mechanics, but it could be simply, the Skull roller coaster thing, then move to skull coaster and enemies, and then skull coaster enemies and jumps...something like that would be fun.