Oh yes, Doki doki. Totally forgot about that one. I liked very much how long this game pretends to be an awful Japanese Girls dating novel, until shit begins to happen. I think this game really only works because it does this not just for a few minutes, but hours.
If you liked Doki, I can also recommend watching The Hex, which also does the creepy meta-stuff quite well. The author released the better-known "Pony island" before, which is basically the same style but it's a bit funnier and the story is not as dark as in the hex.
For the complete opposite, try There is no Game. This one is not creepy at all, but it parodies gaming and its tropes in a really funny and creative way.
I really have to check out the tales series. Have heard a lot of good things about it.

@4 For sure. The only thing that gets on my nerves sometimes is how every single fact is repeated five times, often in the same cutscene. We are not stupid, Kojima.

Some pretty great ones mentioned already, I somehow still haven't played Mass Effect to this day.   

I'll go with Deadly Premonition.  Certainly not for everyone and you have to stick with it, but I'll never forget playing that game with my brother.  It first seemed like a game that was so bad, that it was good.  Later you realize, no, this story.. it's just really, really good.

Honorable mention goes to Lost Odyssey, a game that I don't see talked about too often these days.  Powerful game.  It's been long enough time since I played both, that I would like to revisit them some day.   

I look back on the great ones when I was young,  a few point & clicks stand out.  But then I think about those aforementioned games, other games like Life is Strange, and I realize that the 360 era graced us with some gripping stories.

I love Portal, which my signature proves, but not necessarily because of its story but more because of the humor. Yes, it is not what it seems at first, but in my opinion, the story is still not what stands out about this game. But I've heard Portal being mentioned a lot when it comes to great stories, so this might just be personal preference.
Deadly Premonition! I really have to watch this. I wanted to do it a long time, but I am always a bit reluctant because, as you already said, it seems to be so bad first

A lot of the great ones (Bioshock, Soma, Portal, Life is Strange, etc.) were already mentioned, so let's see what's left! I'll include links to a playlist of the let's play for each game, from Materwelonz. She's decently descriptive, and I enjoy that she thinks aloud a lot about what she plays. But if that's not your thing, there's a lot of other let's plays out there.

The Fall and The Fall Part 2: Unbound: I love stories with AI protagonists, and imo, this one (unlike Detroit: Become Human, ugh) does that pretty well. The first game is a lot less complex, but the second one really picks it up, at parts making you feel genuinely guilty for continuing to play (or listen, in this case) onward, because of ARID being completely incapable at considering anyone else's goals and feelings beside her own. I also love how the major part of the story is interaction *between* AIs, them learning from each other, and not an AI character in a mostly human crew like it usually is.

Final Fantasy VII Remake: This one will likely be pretty hard to understand if you don't at least read up on the basics of the original games on TVTropes. And, speaking of tropes, I've read several criticisms of how full this story is of them. How it might've been good in comparison in 1997, but has not been updated enough to age well. As well as of how badly things like the the Don Corneo plotline are handled. And ... yes, valid, and I agree. But ... Aerith! <3

Little Misfortune and Fran Bow: Are you into horror games about mental disorders that take the cute and creepy and mash them together in the most weird ways? No? Yeah, I didn't think so either, and yet, I really enjoyed these two when I caught parts of them on LevelUpPixie's stream. I haven't watched the full let's plays yet, and this reminds me that I need to. Because damn, they're a trip!

Rumu: A cute little story about a sentient vacuum cleaner that can love! ... Just kidding. As you can no doubt guess from it being placed with several other games with complex stories, this one can't be quite so simple, either. For love is a complicated thing. It can be one of the greatest things about humanity, or one of the worst ones. Perhaps it all depends on who we have as a model ...

Tell Me Why: Another game from DONTNOD Entertainment, the same studio that made the Life Is Strange games, although made by a different part of the studio than LiS. I am no expert, of course, but I think that Tyler, one of the twin protagonists, is one of the (regrettably few) transgender characters done right. He is just a beautiful and complexly human character as his sister. It was really fascinating to watch the interactions between them, both so familiar to each other and yet almost complete strangers after growing up in completely different environments for 10 years. As well, the reminder of the uncertainty of our memories, and the many little (and not so little) ways in which we humans are all broken was really eye-opening. The developers did a lot of research into gender issues, Tlingit culture and mental health problems, and it shows. It's one of those games that we can honestly tell our parents are educational.

Oof. 7 games. OK, I think this might be enough for today.

@targor I'm glad I'm not the only one! She isn't that unknown -- I recall a few other blind people were aware of who she is, and I've seen her mentioned on TVTropes here and there -- but she's definitely not on PewDiePie's level, for obvious reason.

I like that about her, too. She reacts to tense situations, but without going into fake panic mode. She gives off the impression of genuinely being there for the game each time, not to get more viewers or fame. Could be a wrong one, but I don't think so.

Yeah, she describes the things she sees a lot. I love how naturally she does it. Not nearly as intrusive as audio description would be. I wonder if she even knows how much more accessible that makes her videos? I'm half tempted to make a Twitter account just to thank her. Or are you on there and could thank her on our behalf?

@13 Sadly, I don't have Twitter. It's really a good idea. but I must say I'm not ready to enter the twitter hell just yet.
@14 I have watched every Final Fantasy up to 12 and Final Fantasy X did not really have the same impact on me most other Final Fantasies do. I don't really know why that is. The voice acting, especially for Tidus, made me cringe a lot. Maybe that's part of the reason.
I'm very divided on Detroit: On the one hand, I really love how this game finally delivers on the promise that there are many choices and that they really change things, especially in the last third of the game. The music and action sequences are, as usual with Quantic Dreams, top notch. David Cage understands very well how to create awesome and tense action sequences. But the story itself is so full of cliche, it kinda ruins it for me.
Spoilers:
Almost every human is bad as usual, they all abuse their androids, the way they somehow break free of their programming ... and let's not talk about Marcus, who walks around and touches everybody to free them. That takes away everything they built up before with the mental shock and stuff. The game never even criticizes the obvious irony: Now they all fight obediently for Marcus, their new master, just because he touched them and said "You're free". The only really impressive storyline is that of Connor, who is really believable in my opinion.
That's kind of always the thing with David cage: When he has the choice between deepening the worldbuilding and advancing the plot realistically or go for a cheap hit in the feels, he always goes for the latter.

Admittedly, there are some bad bits of voice acting in FFX. You won't see me arguing that. But I think there is also some extremely -good voice acting in that game, which makes up for it.
slight
spoilers
For instance, listen to Seymour telling Kimari that all his people are dead. Listen to Riku freaking out about lightning (it's silly, but it works). Listen to some of the spheres discussing Auron, Braska and Jecht.
end
spoiler
Again, not saying it's amazing, but it worked for me. If you pay attention, there's a lot to be said about the nature of sacrifice and the need for change, not to mention how real the whole thing is.

It's a narrow, flawed, and surprisingly interesting commentary on a whole lot of things. Like I said, I'm not pretending it's the best at anything, but it does work. Do give it another try and let us know what you think afterword. And try not to tip too far either way; it's not reasonable to damn a game for one character's bad voice acting, but nor is it fair to vindicate a game just because of nostalgia. I fully realize this, don't worry. Heh.

@Mayana thanks for the tips about Rumu and The Fall. I have not heard of them before and I was absolutely fascinated by both (or all three) of these games. I agree, when you compare the way artificial intelligence is handled for The Fall and Detroit, The Fall has so much more to say. The biggest advantage here, in my opinion, was that in The Fall, artificial intelligence does not at all behave in a human way while in Detroit, AI is basically human, and not through slow machine learning, but suddenly because of a software problem. Hell, Marcus' first action after his enlightenment is to cry and call his owner dad. That scene was truly terrible.

Wow, didn't think I'd see this topic again. I once watched a playthrough of Fallout 1, but then stopped for some reason. That is a great tip for what to watch next, thanks. Rereading this topic reminds me to finally watch Final Fantasy X again. Still didn't do that. I would also like to add Outer Wilds to the list, which has also been played by Materwelonz. Outer Wilds is a space exploration puzzle game, where you don't progress by procuring more items, but by procuring more knowledge. Every 22 minutes, the sun of the miniature solar system in which the game takes place goes into supernova and destroys everything. Then, for some mysterious reason (which you must find out) you wake up at the start of your journey again. That means you can play through the game in 22 minutes from start to finish if you know what you're doing, but it's impossible to complete the game if you don't know what the goal is. Really awesome game.