This one might be a bit too complex to implement, but might actually work.
The idea is to make some object at the map periodically change their state, so that, e.g. flames burst out and extinguish. To make some areas that have to be moved through in a sequence (kind of a puzzle).
Like this: https://youtu.be/1kdYMtzu-K0?t=23m22s
Also some doors might open and close in a pattern - requiring some timing to pass through and blocking immediate going back, which can be both advantage (to split an enemy horde) or disadvantage, if accidentally caught inside a chamber with nowhere to flee.
In a more complex way, the whole portions of the dungeon might morph in a "puzzle-generated" way, so that they will require some thinking to cross.
It seems this will work best on an hand drawn map.
I think about adding so called 'challenges' which would be small hand drawn dungeons that contain a unique item at the end. Something like this would fix perfectly in there.
It doesn't need to be completely hand-drawn. But a kind of a closed area (like vaults now) with a predefined internal structure (or semi-predefined).