I agree - The Longest Journey. The graphics were gorgeous and the story was immersive.
My only complaint was you sometimes had to play through some really lengthy conversations before the game could be saved. You couldn't exit the conversation and come back to it later.
Other than that, it was just plain wonderful.