Well, multi-character puzzles COULD exist - the problem with XI's 'multi-player puzzles' as some people consider it are just 'I need you to stand here so we can open door'. Which is rather pointless (Garlaige, Eldeime, Quicksands and 3-Mage Gate come into play). That isn't to say that the concept isn't cool and I think for instances the Eldeime and 3-Mage Gate idea could work though Garlaige and Quicksands' is rather pointless. Like, in Eldeieme's puzzle you have to have someone stay behind to operate a switch. Something like that can really be applied in an instance where you'd expect to have more than one person where both players are after the same goal, but not really when half the time it's just so your friend can go through a zone to touch a ???.

Beyond that, yes, make dungeon crawls more interesting puzzles. Put party-required puzzles in instances, and put solo puzzles in both normal areas and in instances.