They take some forethought, I agree. The monster thing is easier done though, the main task is finding suitable monsters, and designing appropriate challenges. The main difficulty here is not for the DM, but the players who need to deal with a slew of new abilities, and more importantly- a radically new body. Some players enjoy this, some less.The monsters thing sounds cool too, but it would be really hard to pull off. Same with the shifting maze.
The shifting maze takes some time to prepare (rooms, connections, content, runes) but is quite easy to run. the main challenge there is reacting to the players' wacky ideas, but isn't it always?
If you're interested i can try and dig through my campaigns for these ideas and help you out. If you prefer simpler stuff, well, that's cool too. You know your group.