An ice Dungeon would be fine. Maybe have the dungeon all ice up until some point where you need to find a key element in the dungeon to remove the ice and turn it to water to continue on and finish. Or even maybe the other way around. Water to ice.
Might make good use of the 256 color spectrum for the combos.
But I definately agree with trying to keep the rooms themselves from being square. Maybe put a little graphical change in the appearance in the begining and advance it further on in next levels.
Having an intro screen could easily give an example of how to input this sort of thing into a quest and might solve the questions about "How do I do an intro?"
