Randomly generated 'themes' of terrain and enemy types that each last 20 levels. At the end of each theme, there is guaranteed a chest with a rod of recall, maybe an elite boss that requires you to improve your tactics, even at normal difficulty. Preferably biased to have slow speed, so you'd at least have a chance to escape and improve your guile before you get slaughtered.
The themes would satisfy both the logical mind and the fantasy.
Adapting to the environment gives you a large advantage if you can manage to exploit your circumstances well enough, it will require you to contemplate new ways of playing along the way, which adds yet another dimension of interest to this already fascinating game.
This could also be a gamemode, but having it inside the world would allow you to still enjoy the locational roleplaying aspect of the game.