I like games where the game itself lets you mold the story, and not be a completely linear path. A good example of this is the Fallout series. Each conversation with a character can end differently, whether it ends with you having more vital intel, extra money in your pocket or getting you killed.
I also like when you get attached to your character. As in, you feel like a friend of the character you play as, and that you feel as if you've grown a bond with him/her. An example of this is "Soap" MacTavish from the Call of Duty: Modern Warfare series...I was kind of sad when he ended up dying in Modern Warfare 3, and that's because I developed some kind of friendship with him during the years.