One thing I did love about GTA 4 was the actual storyline. Those "kill him or spare him" moments, for me, were built up so well that sometimes you hated the bastard so much that you wanted to kill him.
The actual stories and the writing were pretty good, I thought.
One thing, and I've been saying this for a while, that I want in a new GTA: Character creation. Let me make my own guy. Give me customisation options. Let me side with certain gangs over other ones. Let me pick and choose missions that I want to do.
Like, say you're working for the mob and the yakuza as an enforcer of sorts. they both give you missions at the same time, and those missions clash, so if you complete one, you fail the other, so you're scoring both negative AND positive points with people.
Kind of like that mechanic dragon age had, but better.