When cleverly used and contextually appropriate, a puzzle can be integral to strengthening a game's story and the player's experience of it.
Let me be the first to say "OHMYGOD MYST MYST MYST," because these games are the friggin' textbook for puzzles that are integrated organically into the gameplay: engaging and contextual.
I definitely agree that too many games toss in arbitrary puzzles to stall for time, artificially boost the "difficulty" of the game, or just provide cheap, easy-to-make content. Selling a game as having 30 hours of gameplay doesn't mean anything if 20 of those hours involve alphabetizing your weapons or sitting in the final boss's waiting room doing that ridiculous Cracker Barrel golf tee puzzle.
In a well-designed game, puzzles should serve as "quizzes" that determine how well you've been paying attention to the rules and formulas of the game world as you've experienced it so far. Like any good quiz or test in any good class, you should only ever be tested on what you've been taught by that class. (Similarly, the class shouldn't be filled with tons of information that "isn't on the test.")
In Zelda games, for instance, the puzzles in each dungeon are designed to simultaneously teach and test you on the new equipment that dungeon gives you. First, you encounter a familiar task (like hitting a trigger to open a door). Second, you encounter limitations for which you have no solution (like a trigger you can't reach without the hookshot). Third, you find the new equipment. Fourth, you're given a quick task that teaches you how to use that equipment and what clues to look for when you should use it. Finally, you go back to that previous obstacle ready to deal with it. Zelda games tend to be a bit hand-holdy with this in the early dungeons, but later on you're expected to quickly choose from your "bag of tricks" to fit the given situation.
Puzzles engage you and immerse you in the setting, or at least they should. You're forced to learn the "rules" of this world--How fast do you fall? How far can you jump? How many uses does this tool have? How much time do you have before this explodes? What do these symbols mean? Do any real-world rules transfer over?--and then you're put in situations that require this knowledge of you in the context of the game. In this regard, puzzles are a form of "authentic assessment."
An example of "inauthentic assessment" would be teaching you a set of math formulas and then providing you a worksheet of numerical problems in which you use these formulas to generate an answer. An example of "authentic assessment" would be giving you a word- or story-problem in which you have to decide which formula(s) you'll need and apply them in coming up with an answer that is useful rather than abstract. It's not "Do you know this?" it's "Can you use this?" Game puzzles that are constructed (an instructed) with this in mind can elevate a game from "cute distraction" to "thrilling mental workout" without accidentally introducing plain ol' tedium.