Myst is a product of this entirely. The puzzles deal with mechanics, literally, because when you only have one possible interaction with something, "operate" makes the most sense. The nouns you interact with in Myst generally are just switches, buttons and levers: perfect for this sort of set up. This could lead to a purely puzzle based experience but the game deals out narrative in an interesting way: entirely through background text and images. Indirect, like Half Life 2. You don't know exactly what happened, just that something has, and you piece together the story slowly and methodically. You do so by exploring these deserted environments and the feeling of isolation is powerful.
That said, there's a huge divorce between play and story. The hardest part to get used to is that it feels a little like story bits are separated by puzzles. The puzzles are sort of flood gates between bits of narrative. In other adventure games, the puzzles and solutions are often tied directly to what you're trying to do (fool a guard, get a trinket out of a sewer). In Myst, you're often just trying to get somewhere or get past a literal gate. This is jarring if you're not expecting it.
There are some BS puzzles and I mostly favor adventure games a little closer to the narrative side of the axis but this is a must play and available on just about everything.
http://duckfeed.tv/woff/2
Myst was a game, like you mention, that focused on story and the world than most did at the time. It was also one of th first to take advantage of the new CD medium in computers to deliver some amazing graphics.
I remember not being able to play this for a while because we didn't have a PC capable of running it.
Th game seemed like setting from the future with 3D rendered graphics and in game video.
I had a friend that had it and he loved it! I'll admit some of the puzzling elements confused my mind a bit. My friend persisted and he beat it eventually. I think he even did it by himself, which is cool.