if you want old games in particular the first deus ex game is great.

looking through my steam library other games that jump out at me are:

• dishonoured

• the new wolfenstein trilogy

• the skyrim mod Enderal (its not really a mod but rather a game built out of skyrims engine and stuff idk how it works)

• fallout new vegas

• the geneforge series? it gets better as it goes on. not sure i'd recommend any spiderweb software game unreservedly but the overall narrative to geneforge i quite liked

• the half life and portal series are good.

• the new hitman series has a neat story but idk if i'd recommend it solely for its narrative.

• hollow knight has a great story but its not particularly explicit and you have to piece things together on your own a little.

• i liked l.a. noire but it probably hasnt aged so well.

• the mass effect games are kinda cringe in 2022 but still fun.

• i have completed 32 nancy drew games and the stories are kind of repetitive but the characters and settings are fun.

• people really liked nier automata but i dont really remember much of it to be honest

• night in the woods doesnt have the greatest story arc but the character writing and world is really nice.

• psychonauts might be hard to go back to but the character writing is fun and quirky.

• pyre is my favourite supergiant game (i havent played hades tho)

• if you like western RPGs the shadowrun series is really good (although the first in the series, shadowrun returns, is kinda so-so).

• a short hike is mostly gameplay but again the characters and world are well written

these are all steam games though. there might be stuff on consoles that im not thinking of.

right now im playing murder by numbers, which is a murder mystery mixed with picross, and i'm enjoying that, too. i'm not sure the storyline is like, Good in the traditional sense, but its got intrigue and mystery and a fun gay best friend character so i'm having fun for now

big seconding for the Shadowrun series, I personally say skip the first one (Shadowrun Returns) because it's short, muddled, and kind of more of a proof of concept. Shadowrun Dragonfall is my favourite single player video game of all time, and I particularly like it because of the writing. The story is quite neat, I think it does the slow dive into a conspiracy angle quite well. I thought it was really refreshing how your motivation for most of the jobs is just needing the money and doing what people ask, and several of the scenarios contained genuinely difficult moral choices rather than the usual video game fare of "do you want to kick the puppy or save the puppy" and a lot of the time when there's an obvious third option, the game will let you do it but it's gonna be a lot harder to pull off. Shadowrun Hong Kong is imo a bit more user friendly, as they tidied up the interface and added a couple of nice quality of life changes, but I prefer the writing in Dragonfall.

If newer games are okay to recommend, I've been quite enjoying the story of Scarlet Nexus, but in a very different sort of way. Every single story act has several twists in it, and just going along for the ride and seeing what levels it escalates to next has been quite fun. I'm really near the end at the moment, and boy howdy if you'd explained the story to me after I'd just started playing I would not have believed you.

Morrowind has some alright writing, the main quest is good if you really dig deep into the lore and think a lot about the narrative. I can't really recommend getting into it now unfortunately, but I can very much recommend retroactively spending hours of your childhood obsessed with it.

I'll also second Mass Effect. They're pretty dated, and I'm actually replaying them at the moment (skipped 1 because I just cannot deal with it, but the legendary edition apparently makes it more palatable). Mass Effect 3 had a moment in it that genuinely made me cry when I first played and I'm not embarrassed to say so.

Gris isn't a very narrative-heavy game, doesn't have a lick of dialogue, but nonetheless tells a story very very well.

Also, I cannot emphasize this enough: I love love love the very pen-and-watercolor geometric / astronomical / architectural style they have. It is satisfying in a way I can't really express.

Another game, Metroid Dread, I found the story to be extremely satisfying for some really silly reasons. It's not a good story but it was satisfying as someone who has been invested in the series for two decades. Especially how they portray Samus. But I can't explain why without spoiling the game.

most of my favorite stories in games have already been suggested here, but one i didn't see mentioned yet is Hellblade: Senua's Sacrifice. it's a violent and emotionally heavy story. i can't recommend it to everyone for that reason, but it meant a lot to me when i played it.