I value story and writing very highly, too, Terramax! Thanks for starting this thread. IMHO, the best stories are in the older adventure/puzzle games. If you like Gabriel Knight: Sins of the Fathers you should definitely try the Tex Murphy games. Cleverly written mystery plots, with the wittiest dialogue trees you'll ever find. The old Sherlock Holmes adventure games are in the same mold as Gabriel Knight. I loved Shivers and Shivers2 - rendered screen puzzle games with an entertaining story to discover. Black Dahlia has an incredibly deep and well-researched historical plot, but extremely tedious game mechanics. Worth trying if you can find a copy. Bladerunner is also worth a look, bearing in mind that it's more like an interactive movie than a game (not really a lot of decisions to make, but tons of story). If you like the funny old LucasArt games, the best of them all is "Day of the Tentacle." It's sophomoric, but I couldn't stop laughing. Oh, and Dark Earth, which is sort of like Fallout (only completely different). Best of all, all of these games are dead cheap if you can find computers old enough to run them. So there's little to lose by giving them a try.
Moving to action/adventure - for me Realms of the Haunting was an epiphany. I got so sucked in by the deeply creepy, very complex story that I overcame my fear of 1st-person shooters and eventually went on to things like Half-Life (which does not have much story at all, that I can see, but has one hell of a BACKSTORY). Other people have mentioned the sneaker-shooters from Looking Glass and its descendants (Thief, System Shock, Deus Ex). Deus Ex is the best game EVER. FPS fun in the Half Life mode, but with story and character development that leave Half Life in the dust. Deus Ex is better than its sequel, but both are great.
Here's one final recommendation that nobody else is going to mention, but until I played Deus Ex it was my favorite game of all time: Azrael's Tear. It's an obscure DOS game from the mid-90's. It's a first-person adventure game with occasional easy action sequences. Mostly it's story, puzzle-solving and exploration. Lots of games use the Knights Templar mythology as a background, but this one gets it right. The last dozen or so survivors from the Templar massacre have been holed up in the caverns under a Scottish Rite temple for 600 years, and none of them are exactly playing with a full deck any more. You meet them one by one and hear different sides of the same story and eventually have to choose sides. The story unfolds in a non-linear fashion through conversations and scraps of parchment which can be discovered in any order as you complete side quests. There were times in playing this game when I could literally feel the hair rise on the back of my neck, and the denouement blew me away: all through story, not pulse-pounding action. If you can find this game somewhere, and dig up a machine antique enough to run it, you should play it!