Over the years I became more and more story-oriented. Well-integrated puzzles that make actually a lot of sense in the story, oh yes please. By now I've had my fill of the weird object combinations and the tired old variations of ancient stand-alone puzzles. So for me it's:
Exploration + Story + Atmosphere = Immersion