I'm sure that some (if not all) of the games I'm going to recommend were already mentioned but I will do it anyway :)

The Wolf Among Us - practically interactive movie with some quick time events.

Blackwell - even though I don't like adventure games, I like this series.

Shadowrun Returns and Shadowrun: Dragonfall - I like the first one more. I think that the "Returns" has good and compact story (at least till we find the killer, after that it turns into weird s-f horror), but I higly recommend both.

Witcher 2 - good and not too long story.

Hard West - Mix of turn-based strategy and text adventure. The game is divided into few separate stories, but be warned, they are quite depressing.

And of course Planescape: Torment - great story, great characters. A must-read...yyy I mean play.

Psychonauts !

(what? it has a good and funny story. Beware the milkman!)

For GOG:
I found Dust: An Elysian Tail to be touching and adorable. :)
Link: https://www.gog.com/game/dust_an_elysian_tail

I couldn't agree more about The Longest Journey and the Shadowrun series.

There's also a free visual novel on GOG, but I haven't played it yet, so I don't know what the story is like.
Link: https://www.gog.com/game/sunrider_mask_of_arcadius

For Steam:
If you like the sound of a game with much dialog and a story that's a cocktail of Japanese myths and tales and has a great soundtrack, I'd reccomend Okami.
The PC port is good and don't worry about the system requirements, they're overblown.
Link: https://store.steampowered.com/app/587620/OKAMI_HD/

If you're willing to try games that are like visual novels, but lack the music and mostly don't have illustrations, check out
The Great Tournament series by Choice games (the tag says "Hosted Games", but it's a smaller branch of the same company) or some other of their games.
Link: https://store.steampowered.com/app/800050/The_Great_Tournament/

Other:
If you're willing to check out visual novels, Ripples by sakevisual might be a good first experiance.
Link: http://www.sakevisual.com/ripples.html

Dragon Age is good. Wait for a sale and pick it up then.

I would say, "The Raven" has a nice story (I enjoyed it - I could easily imagine a movie being done after this):
https://www.gog.com/game/the_raven_remastered

I rember some of its games.
I never got too much into them because I never owned all of the PS2 copies.
There's a video on youtube with a "movie" that shows how the story went chronologically.
I don't recall how long it lasted but it was long.

I'm not sure if Legacy of Kain would be good to dive into blindly. You'd need to look up timelines and see what happens when in each game to follow, the story is too fragmented.

Wizardry 6 is still mostly dungeon crawler. Wizardry 7 has a bit more story. Wizardry 8 is basically Star Wars in the form of an open world dungeon crawler. Though I'd rather categorize that as "good lore" rather than "good story".

How could I possibly forget?!

Neverwinter Night 1 and 2 are both here on GOG and you can even add more story content with mods.

NWN 1 link:
https://www.gog.com/game/neverwinter_nights_diamond_edition

NWN 2 link:
https://www.gog.com/game/neverwinter_nights_2_complete

I've only played a bit of it offline once, but Inuit myths and tales are plenty in Never Alone.
Link:
https://www.gog.com/game/never_alone_arctic_collection

Not really. I wasn't a Star Wars fan before KOTOR. KOTOR made me a Star Wars fan
I stopped playing Ultima 7 for the time being due to real life circumstances. It has very good writing, honestly the writing blows my mind. It feels like the first time playing Morrowind again. But yeah, it's not easy to play. I have to consult to walkthrough because the hint while very clear is also indirect. For example the King would say where hero's friends are but never mentioned that we should go recruit them.

If OP wants to play Ultima 7, I really suggest using Exult, turn on smooth scrolling and set game speed to 8. Also learn a few shortcut like K to try every keys, C for combat etc. After that the game should be closer to a modern game. I still don't like the inventory system though

Kingdom Come Deliverance.

It was late, I meant Fallout 3 over New Vegas. FO4 I actually like as well despite its flaws.

As for FO1&2, I haven't played them - though I own them. I started FO2 and just the interface alone gave the feeling of 'this is going to be work to figure out.' I may like it when I give it more time but from a modern perspective of someone that didn't play CRPGs during that era there's a bit of friction. FO3 had some memorable DLCs and quest lines. Also I suppose it depends on what 'story' means in a game to you. Reading boxes and boxes of text is story to some but in a game for me there's a visual component that should be used to tell that story. Bioshock is probably one of the best examples of a rich story that is mostly told through the exploration and visuals of its environment. For me that's part of the attraction of an open world game like FO3.