Give their mapper fits: you can use the door in room A to go to room B but if you backtrack through the same door you end up in room C, going up the stairs leads to the basement, magnetic north shifts when they make camp, etc.

Make magic unpredictable: energy types change, casters much make spellcraft checks or will saves to avoid having their spell behave like a use of a Rod of Wonder, etc.

Make using diplomacy or bluff on the locals difficult if the players behave as if they're dealing with rational people. Give unattended object the chance to become animated and cause confusion.