There should be levels with some problem solving, and the problems should get harder as you near the core. Excuse my grammatic mistakes -.-
* Ice, and you have to figure out how to get to the other side by sliding on the ice, thus hitting blocks stopping your movement. (I thought of pokemon lol)
* OPTIONAL riddles leading to special areas with awesome rewards and monsters that you wouldn't normally see
Yap yap yapp... Too lazy to write more :/
I would LOVE more puzzle/problem solving. There are a few sections, even the switchback is one of them, where you have to use gates etc to get to what you want, and then putting the statues on the trigger buttons, but I really would be happy with more. I don't know that I'd necessarily have them be mandatory for the completion of a level, but puzzles that allow you into "select" areas of a map, or access to special treasure would definitely improve "replayability" for me.