As a guy, who was dissapointed with GTA 5 storyline, I'm sayin'
I'd like to see main character deeply involved in organized crime, like Cosa Nostra, Black Mafia or Irish Mob, rising through the ranks in organization during the storyline, depending on player choices of course.
Speaking about setting - it would be real interesting to see new GTA game set in 1970's, for example in Liberty City again.
Liberty City Cosa Nostra plot with Five Families could be a perfect prequel to GTA 4, explaining much LC history in HD Era.
As an alternative Rockstar could choose cities based on Philadelphia, Baltimore, ect. Or depict full State of Aldreny (based on New Jersey, including Southern part, like Atlantic City).
The storyline, in total, gotta be as dramatic as GTA 4 was.
All due respect, that would be much more exciting and interesting, then the present time story line, based on sci-fi bullsh*t, with jetpacks, military aircraft.
And, in my opinion, it is better to have only one character, but with strongly developed personality and pre-history, then the angry fella from the hood, psychotic drug-addled cross dresser and midlife crisis ex-bankrobber (who, btw, is the only of them three who deserves to be called the protagonist).