I think I can only repeat the previous ideas.
Homeworld
Knights of the Old Republic (and its sequel was OK)
Deus Ex
Baldurs Gate 1,2 and expansions
Max Payne 1 and 2
American McGees Alice
Clive Barkers Undying
Alien Vs Predator 2 (not too complex, but well told)
Call of Duty 1
Medal of Honor: Pacific Assault
Elder Scrolls 3 and 4 had fantastic stories, but they dont play out for you. You have to go and find them yourself.
Fallout 2
I thought Freelancer had a decent story but like the Elder Scrolls games, too much wandering around and slow time to make it cohesive.
Full Throttle
No One Lives Forever 2 (parody of 60's/70's spy movies, fun)
Septerra Core was a japanese-like, consolish RPG title with a better than average story.
Tron 2.0
Total Anihilation: Kingdoms. It isnt exactly an action-packed story, but the cutscenes in between missions are suprisingly professional and interesting.
I thought the story in Unreal 2 was actually good, but most folks remember the action.
Neverwinter Nights 2 is alright, and the expansion improves the story and storytelling a lot.
Overall: I pick Deus Ex. When you start to figure everything out it will BLOW YOUR FUCKING MIND MAN!