I'd just copy exactly what's in M&M 3-4-5, it works in these games with the same premise so it'll work here, for example :
- a cave where the walls fall in the corners as you move around, revealing a eventually larger and larger "arena", this works great in these games
- need to cast a levitate spell and walk of water spell, don't hesitate to double hint that you need those if you feel like it
- you can have an area with diverse NPCs saying something and you need to make something of it, which can for example be a prison where the various prisoners heard some discussions from guards about a code ("first digit is odd" "second digit is lower than first" "second digit is twice the third one" "fourth digit is the highest one" "sum of the digits is the smallest number using two digits").
- big cups, you need to drink them all to open a door but you get sick when doing so anyway
- I can't remember if you have fountains to temporary raise each attribute (spell is fine too anyway), if you do then an attribute test for each, possibly to pay homage to a statue for personal experience,
- you can also have a sword to take with high strength or a glass to break with high strength
- arrows you need to turn so that they all point to a central point
- dungeon with an elevator where you're looking keywords to the different floors
- one place can have cursed fountains but one is blessed, with a hint that they're cursed when you enter and the hint one is not somewhere else
- one dungeon where you need to place 4 orbs to access the main area, the orbs can be either there or spread over the world, in which case someone must give you the information of where each is (both types are satisfying, one dungeon where you do 4 quarters to reach the end is cool)
- one lever puzzle where each lever activates (open if it's closed, close if it's opened) two doors, might also be two wall parts
- one cursed place where taking golds make you lose gold instead
- the thrones where only the right character could sit to gain experience were cool too
- some illusionary walls, I think these you can have from a few to a lot, either way can be cool
- some sparse spinners near the very end of the game
- if you have keys to enter various areas, then you'd better double hint the location of the keys, that's how these games do it
- in the same vein riddles with the word to answer available in the game somewhere is also the way these games do it ; I doubt the game was the first time someone said "The more of it, the less you see." so I would be concerned about it fitting the fantasy theme much more than about trying to come with some super unique one which was never done, if a couple of ones I would definitely mix some where the answer is some actual name from the game and some more general but fantasy ones
- one word to enter a secret cave, written on a paper in a prison or something like that
- statues you need to pay homage to in the right order (for example with colors and RBGPO, something like that), but drums to hit might be more cool than statues in fact
- If you want coded messages, some possibilities are : stuck the words and/or reverse the letters, need to read from top to bottom then left to right instead of left to right then top to bottom, add a word between each two words, just mix the letters of each word, separate the vowels and consonants
- ...
I think these things fit the legacy, premise, difficulty and target of the game, they're all meant to enhance the pace rather than breaking it.