I'll chip in and talk about a few great games with good gameplay and storylines:
1) Neverwinter Nights/Neverwinter Nights 2: These are RPG classics. IMO, no RPG till date has come close to the storyline depth that NWN2 had. Not even the witcher......The gameplay is based on D&D style, so it may pose some problems....but you'll get through (combat has a steep learning curve).
2) Cryostasis: Sleep of Reason - *Very* well done storyline.....but it's more of an exploration and horror game than action. VERY SCARY!
3) Rainbow Six: Vegas and Vegas 2 - Good, modern, contemporary story and good team-based action. The graphics still look very good in some places for a game released in 2006 (Vegas 1). The artwork and colours are really something special, it's great to look at the environments in this game.
4) Splinter Cell series - Although it's a stealth series, the storylines in the series are usually VERY good.
5) Call of Juarez: Bound in Blood - Let's just call it COD: MW set in the 1800s. Good old western FPS, very good story.
6) Titan Quest - Another good RPG.
7) Far Cry 2 - Frustrating as it may be at times, this game has a very interesting story that will keep you thinking for a while. The only problem is that the story only hits you after you finish the game
Off the top of my head, only these games come to mind apart from what's already mentioned as far as story-driven games go....but I guess this much is enough