You're probably right. And that illustrates why it's hard for me to get back into gaming again: it would be like trying to get back into the music I liked when I was 16. That scene is certainly still active and some of the music is probably good, but they have moved on and I have moved on, and the gulf that separates us keeps expanding.
Around or after 2000, it seemed that there was nothing left but first-person shooters. That probably wasn't true, but I wasn't interested enough to discover the other stuff, and so I stopped playing games. So I've never had enough desire to try Half-Life, GTA, or any of the other 3D titles that appear to be basically Doom with a handful of storyline elements interspersing the shooting.
If you ever get the time, I feel like Half-Life would be an awesome play-through for you. It really is the #1 FPS in terms of story for me, and I've been playing through the new Black Mesa port (it's HL on a newer engine) and it's been great.
HL2 is practically unbeatable in my mind, I sound like a fanboy but it and its Episodes are really an amazing series of games.
They are extremely good at putting you in the mindset of Gordon Freeman and at creating a sense of being chased and action while presenting very relatable characters.
Also, if FPS really has you that turned-off, there has been a great revival of strategy and Rogue-like indie games recently. But it all depends on what you're interested in.
If you hate action and want to be impressed by an immersive FP experience, look at Gone Home.
I think pavlov likes games with a defined, fleshed out protagonist, and Gordon Freeman is pretty close to a blank slate as you can get.
As for recommendations, pavlov hasn't mentioned any genres or games that he particularly liked. Adventure games were pretty common back then and "died" around 2000, so I suggest looking into anything by Telltale Games or Double Fine.
I was in much the same situation. I dropped out of gaming around the time of quake for much of the same reasons, repetitive shooting, focused on how fast you can respond instead of on storyline and puzzles.
But, i've gotten back into things. I've really enjoyed both portal games, and following that asked around for something that is story-driven and got recommended the mass effect trilogy. I've since played through mass effect 1 and 2, and while there's a lot of shooting involved, the shooting makes sense as part of the story, and you are never forced in situations where you have to rely on reflexes. The mass effect storyline itself is fantastic. It's a grand adventure that unfolds over the three parts, and i'm really looking forward to playing part 3.
Edit: another game that i really liked focused heavily on puzzle solving with a decent storyline is mirror's edge.
If you don't hate jump puzzles, you'll probably like FEZ (by Polytron Corp.). It doesn't have much of an explicit story, but there are things scattered here and there that do a bit of world-building.
Psychonauts (by Double Fine) might be too shooter-y for you, but I'm really fond of the strong characters that you meet throughout the game (each with a backstory of some depth).
Both of these games are pretty cheap on Steam, if you're not opposed to using Steam. They both run on Windows, Mac, and Linux.
Your post sounds an awful lot like "they stopped making good music back in [year I graduated high school]."