One game that springs to mind was Omikron: The Nomad Soul. I only ever played the DC version, and I've been reluctant to pick up the GOG version for fear of becoming bored early into a second playthrough. Anyways...
For all its flaws, that game did a damn good job of unnerving me something massive when I played it. It was an open world to a degree, before I'd even played GTA III (you couldn't jack cars, but you could take cabs, if I remember right), which was impressive enough, but then I wound up in a situation that got who I thought to be the protagonist - Kay'l 669 - killed early on. My first reaction was panic, because I think I forgot to save for some time and I thought it was going to be a straightforward "game over", but then SUDDENLY, some thief comes along, only to get herself possessed by what I soon discovered was the true protagonist, that being the player.
It's difficult to explain, but it was refreshing to discover that I wasn't bound to a single preset character, in spite of the possible pitfalls that Quantic Dream threw in to limit the reincarnation system - for example, the process destroyed the old body and made it impossible to return to, so you had to choose whether taking someone else was worth the sacrifice. The protagonist was essentially yourself as the player and the storyline cemented that by taking the classic kid's cartoon plot of the game being a portal to another world and reworking it into this nightmare dystopia. Granted, it wasn't perfect, and some character dialogue came across just a bit creepy at times, but still, at the time I don't think I'd ever seen a game do anything remotely like it, and you still don't to this day.