None of these are a 100% fit, but they might take you interesting directions.
Obduction (good voice acting, FMV, exploration, physics/logic puzzles... Essentially the Myst of our time).
Legend of Grimrock (turn based, throwback to Eye Of The Beholder-type games, pretty good environment/clue-based storytelling, fun switch/lever/hidden/mind puzzles). There's also
a sequel with better graphics, different story, more advanced puzzles).
Portal (good story, exploration, physics/logic/skill puzzles, cake) and
Portal 2 (pretty much the first game, but mooooore, and better in every way except for one annoying character).
Alice: Madness Returns (sequel to American McGee's Alice, third-person platformer with cool worldbuilding, decent acting and puzzles, competent combat).