The Longest Journey and its sequel, Dreamfall
This world, the world of science and technology, exists parallel to another physical world, the world of magic and fantasy. You are pulled from one to the other, several times, as mysterious forces arrange for you to fulfil your destiny and save the Balance of the worlds from other forces that seek to abuse it. Believable, sympathetic and interesting characters, a setting that alternates very effectively between enchanting and foreboding, and an intelligent, existential mystery that unfolds at just the right pace, all conspire to bring this adventure game franchise alive.
Syberia and its sequel, Syberia II
A corporate lawyer embarks on an odyssey across Europe and northern Russia in search of the heir to an esoteric toy-making business which her client wants to buy out. It becomes apparent that her quarry, a lovable genius savant, has laid out a path for her to follow, making use of all his marvellous, clockwork-steampunk inventions, and along the way gradually builds to an epiphany wherein she shuns her materialistic past and embraces a deeper truth than her previous occupation could provide. A beautifully told story of a gradually-building, deep, platonic love between, not so much a woman and a man, but a woman and an idea. An adventure that frequently uses puzzles as expositional plot devices to excellent effect.
Deus Ex, and to a much lesser extent its sequel, Deus Ex: Invisible War
Basically, 1984 crossed with The Matrix. The very effective illusion of choice and immersive gameplay really flesh out the deep, intelligent, philosophical and very well researched story of a near future corporate/government conspiracy in this role-playing shooter. Good use of many variations on the "dying log" trope, which the player is free to ignore but which otherwise give the story another whole layer or two of depth.