System Shock 2. The main plot was certainly interesting, but I was really taken by the crewman vignettes: The panicked scientist trying to objectively describe the digestive tract in which he is trapped, the two lovers trying to find each other in the carnage, even the researcher wondering where her nursing staff has gone. I don't play the game any more, but I do listen to the audio logs as a kind of radio play.
Avernum. The world and the plight of individuals within were described well. I often found myself imagining it well after playing.
Gothic 1 and 2. Again, the world is really nicely done and the inhabitants are gritty and a grim and so unlike the flat characters I meet in other games.
Now that I reconsider, I don't think the central story in these games is as immersive and memorable as the small stories told within. I definitely fell into these games, but maybe I should attribute that to convincing world rather than terrific story. They're hard to separate, I guess.