I've decided to make it a sort of mini platformer type game, along the lines of "Wonder Boy in Monster World" (imho a Sega Master System classic). This game had reusable rooms, I'm presuming to save on the space requirements, while allowing a maximum amount of game play. In any case, I enjoyed the way that you would revisit familiar areas and find something new to continue your journey through the game.
This design would require a level editor, or at lease some drawing skills to figure out. I decided to use MS Paint to make some simple blocks, and MS Word to put the blocks in place. This worked great, and fueled the ideas some more.
Here's the final result of my tinkering:
The way I figure that it will work is that as you go through the game, you collect various "treasures" from each of the bosses.
1) White Dress - Allows you to walk on water
2) Harp - Allows you to break ice bricks
3) Halo - Allows you to stand on clouds
4) Wings - Allows you to fly
As you can see in the picture supplied, each of these features would be used in this 'main room', to gain access to the next room. Going though this room will allow you to access the next boss, which would then in turn give you the next treasure.