You seem to have the same wants I do when I play an adventure game.
I'll echo some of the suggestions here, primarily:
Under a Killing Moon, The Pandora Directive, Overseer (Tex Murphy 3, 4, 5) all are available at Good Old Games
www.gog.com at a discount. Plus the oldie but goodie 1 and 2 are free. These are a must play. Good stories, good puzzles. The Pandora Directive is, in my opinion, one of the best adventure games of all time.
Gabriel Knight 2: The Beast Within. Maybe the best overall story in an adventure game, incredible music.
If you don't mind a little THINNER on story but good atmosphere/puzzles/music, then Shivers 1 and Shivers 2 are worth a look. Mostly a series of puzzles, but pretty fun to figure out type, at least to me.
With that said, if you haven't played Myst (also at
www.gog.com), it's worth a try. Again, slimmer on story (though the world is very deep), the atmosphere/puzzles/music are good. Riven increases the story some.
The Journeyman Project 2: Buried in Time also one of my favorites. Hits on all the points you want, maybe a little thin on atmosphere since it's one of the earlier FMV/CG games and had a smaller game window.
