As corny as this will sound I think, for the most part, that the likes of Final Fantasy are the only games that really mastered story telling in the sense that you actually begin to feel for the characters.
FPS's and the like (such as Bioshock and GTA mentioned), to me, are almost devoid of story due to the game to constantly need to get the player shooting things and blowing things up, rather than creating a character to warm to.
Also, as Dreddz rightly put, Silent Hill (peaking at 2) was another example of decent story telling due to the game continuously keeping you guessing, and not shirking from reality.
Bring back more story please. You dont have to shoot everything to get a good interactivity!