For starters I would really vouch for Dragon Age. If not a masterpiece, it's a really interesting story.
If you're into Rock/Metal, I'd suggest Brütal Legend. That game
I love it. Don't expect a truly amazing story, but I have to admit it's fun and the atmosphere is, well.. self-explanatory. A hack and slash, also the boss encounters are easy once you figure out the tactics.
A game hard enough to actually become quite memorable will be Dark Souls. But it might as well make you give up on life.
As I read a comment somewhere "I'm on the tutorial and I already died 4 times." I died too
Sadly, my recommendations in relatively new story-driven games are scarce. If I want a storyline, I play really old games. New titles just don't cut it... So I turned to MMOs.