Myself, I'm all about the setting and the story. The dime-a-dozen sword & sorcery games out there bore me to tears, but Fallout was one of the best games I've ever played. With that in mind, I'll recommend 2 more of the best games I've ever played (although I'm stretching the definition of "RPG" a little):
I just finished Deus Ex: Invisible War, which wasn't quite as cool as the first one. If you're not hung up on state-of-the-art graphics, I'd go with the first one (which is simply Deus Ex). Both are first-person RPGs, with some puzzle-solving, some stealthing, some shooting, and some hand-to-hand fighting. I imagine you can get a used copy of the original on Amazon for a song.
Chronicles of Riddick: Escape from Butcher Bay is relatively short, but I thought that was a plus. Most games spend too much time doing nothing (it sounds like Planescape: Torment, with it's "prebeginning" would make me insane). Some people didn't like the game's brevity, though. It's a fun combination of a shooter and a stealth game, with great graphics and a cool premise (you play as Riddick and in the opening sequence, you get thrown into a "super-max" prison known as Butcher Bay). You don't need to have seen or liked the movies to enjoy the game, I don't think (I liked the first movie, not so much the second). It has a nifty hand-to-hand fighting system, too. I haven't played the "Developer's Cut", so I don't know what that offers.