I for one absolutely love the freedom and sense of exploration of this game, but much like A Link Between Worlds (another crowning achievement of gaming, mind), being able to do everything in any order runs into a pretty big problem that nobody has been able to solve yet: lack of escalation. Simply put, if every dungeon is objectively equally difficult, then the last ones you complete will subjectively feel much easier than the first ones, both because your character is stronger and because you're more familiar with the game. Normally in a game you want the opposite.
Regarding puzzles, there's not much that can be done to alleviate this beyond actually having different puzzles dynamically swapped in depending on how far you are (and that way lies madness). Enemy-wise, BotW tackles this pretty well on the overworld with progressively more difficult ones, but between dungeons having very few enemies (a problem in itself) and these enemies not escalating, the later dungeons feel like a pushover and aren't very satisfying. I wouldn't surprised if that's the entire rationale between having only four of them and them being short, so that not a lot of development resources are spent on something that will ultimately feel like a formality.
Another approach may be something like having multi-part dungeons, where the first half is a sort of introduction for a particular technique or new item and is available from the start, and the second half is harder and makes you use that technique in more complex ways, but is only unlocked after a particular global progression point. If you're already past this global point, any new dungeons you discover can be played through from start to end. People aren't usually fond of backtracking, though...