a maze is just about finding the correct path to the exit, so like where to turn or in this case which modes to use to progress the path.
a puzzle usually has a moment of insight for the player to uncover. For this to happen it usually feels like the puzzle is impossible (even for split second) or you're completely out of options at some point (not just about turning different corner) then you realise you could do something that you haven't done before (the a-ha moment)
when watching people play the best puzzle games you'll see them get stuck for a little bit before it finally hits them (they'll start with trial and error but hopefully find the actual solution through creativity)
its also a lot of fun designing levels that try to inspire such a specific feeling in the player