Try considering the first level where you actually fight...there technically wasn't any fighting in the very first level of Half-life, and I definitely died a couple of times the first time playing through the first level in Half-life. I didn't come close in the NOLF2 demo...
Speaking of character-driven stuff, there's one game that I never bought that I would like to get sometime, just for that reason: Deus Ex. Additionally, Half-life did have a fair bit of character driven stuff at the very beginning...I'm mostly disappointed that it fizzled out so quickly. The greatest thing about Half-life was that you didn't have to read anything to figure out what to do...most of it was people talking to you, which I feel is far more immersive.