And I don't see how any of you has addressed Horsie's initial comment: Tower of Hanoi-like minigames are shit, whether they appear in a Myst-like, in an IF game, in a "traditional" adventure game, or in KOTOR.
Probably because most people posting in this thread agreed that minigames are shit. And if you want a Myst-like with minigames, Myst isn't it. Shivers is it. 7th Guest is it. (Actually it's probably more accurate to call these ones 7th Guest-alikes; Shivers was pretty much Sierra's answer to that.)
In one of the ages of Myst (Channelwood, I think it's called, it's been a while since I've played it), pretty much all of the puzzles are exactly what Andyman was wanting: they're perfectly integrated, as they're all about powering up machines by directing water along various pipes. Given that all the people that used to live there are all gone, it's not all running, so it fits perfectly well in with the world you're presented with, and it fits in with the story because, yeah, the brothers weren't known for their compassionate behaviour. Another age, again, is about mostly controlling pumps, which again are on an abandoned world and so there's probably only enough power to do one properly. Another age (the Mechanical age) has you, again, just trying to figure out how to use machinery to rotate a tower. That's pretty much the puzzle of that age, aside from getting a combination to exit again (which I'll address in a bit). Again, it's integrated pretty well and suits the story for that age. Even the combination to escape does kind of fit, as there was a war going on and I doubt Atrus wanted any of the "pirates" to come through to other worlds (although the location of the clues for it are in a bit of a bad spot for that). In fact, most of the puzzles involve figuring out how to work machinery.
And on further reflection, there really aren't all that many puzzles in Myst.
And you know what, even though I don't entirely agree with the argument myself, there is one to be made that, yes, the weird abstract puzzles of Myst actually are integrated with their world pretty well. You're Atrus, you're apparently a smart enough guy to write links to different worlds, and you're not the only one. You can't very well just stick all your linking books into one big safe marked "IMPORTANT AGES DO NOT STEAL"; you have to hide them because you're not the only smart world-linking guy who's out there. The puzzles are abstract because they're essentially combination locks (in fact, they are all pretty much literally that, as far as I can remember); and they're hidden within the world for the same reason you hide your safe behind a painting or a secret wall: so nobody realizes that there is a safe there at all.
Now all this isn't explicitly told to you; but that's why you have the note telling you to look under the dock. That's why you read the unburned journals in the library. Granted, it's not a standard way of telling a story; and it's far more archaeological in nature, but to dismiss it as an abstract puzzle game despite the fact that these things are included and there is a reason for their existence? That just seems to stretch it a bit for me.
I do agree that adventure games aren't necessarily defined by their story, though Zork is a borderline example if you consider IF to be its own genre, but even then all the original Sierra adventures (Wizard & The Princess, KQ1, Mystery House, etc) were more adventure games than puzzle games, despite having extremely minimal story (well, KQ1 probably had the most elaborate, but that's not saying much).
This was my big problem with what Andyman said, aside from him making some statements on Myst that I tried to provide counterarguments earlier. It's like saying cRPGs are defined by their stories, when some have hardly any and are still good, and the foundation games of the genre didn't really emphasize that as much. The story of adventure games is a tool of the genre, not the raison d'etre of the genre. That limits the genre for no good reason, other than your own personal preferences.
Both Zork and Myst have puzzles to solve, and even more fundamentally than that, both involve exploring a world at its core. It doesn't matter if Zork is an "interactive fiction" as a subgenre or a separate genre: they have a fundamental game feature in common, and it's stupid to argue otherwise.