I'm not a big fan of "cinematic" gaming (movie or game, pick one) but I actually enjoyed the story elements in GTA4. Like Nature Boy, I really dug all the little conversations you'd have with people. It really draws you into the characters and you end up actually giving a damn about the as you learn their motives and their characteristics, not just you care about them because the game tells you that you have to. Plus Brucie always cracked me up.
I still don't think it's a 10/10 best game evar, but it is a really enjoyable game. One of the rare instances where I paid full price and feel I got my money's worth.