Aura: Fate of the Ages is a good adventure game with an emphasis on puzzles over story and exploration. In fact, the less-than-stellar reviews it received are generally based on the fact that it was so much of a puzzler that it was hard to even call it an adventure game. But the puzzles are good and challenging so he might dig it.
Neither of those games is for people who don’t like non logical puzzles, because they are absolutely filled with them. I love both of them, but they sound like a bad matchup for what you are requesting.
I didn’t find Grim Fandango’s puzzles to be any less logical than the original Myst – both had puzzles with obscure solutions, but they had internal logic.
Most of the recent & semi-recent classics have been covered. Sanitarium, Myst 4: Revelation, and Obsidian have been well reviewed, but I haven’t played them. Obsidian mixes logic puzzles with those that need hand-eye coordination, so this might not be a good fit.
I don’t remember hand-eye coordination puzzles in Obsidian. I heartily recommend it though, as it’s one of two “Myst-like” puzzle adventures I’ve ever finished (the second being The 7th Guest, which I’d also recommend).
How about stuff like Gabriel Knight 3, Rendeszvous With Rama and the like too? Sierra had quite a few (stay away from Phantasmagoria, though… bleh)
Of course, I have no idea where you’d find these things other than used these days.
I wish I still had my copy of Obsidian, but it got loaned to the ex’s father before she was the ex, alas. (And it’s kinda okay; her dad I liked a lot. )
As mentioned above, I’d recommend Syberia (and its sequel Syberia 2). They stand up as, arguably, being the best the Adventure genre has to offer. An interesting, original story combined with some not-too-difficult puzzles along the way.
There’s a fun puzzle game called In Memoriam (it’s called Missing Since January in the US). It’s not an adventure game, but it’s based on logical puzzles and searching for clues all over the internet and in puzzles that are in-game. The story involves a Da Vinci Code-esque cult, and the kidnapping of 2 journalists.