Give it a theme (fire/ice/prison/cave etc.) and keep it consistent. Make sure the puzzles show some creativity, not just "step on the switch". Add some variety to the traps, surprise spikes, falling boulders... Add some puzzle enemies (fight your way through an absurd amount of enemies or drop the ceiling on them, flooding the boss' room with magma instead of attacking him...).
Some people like timed dungeons (usually the escape-before-it-collapses type), you could try that. Be sure to make it long enough, but not too long that they don't feel the need to hurry.
Music is very important to set the mood, makes sure it fits the environment.