I agree, gta4 was an awesome game, I 100% completed it because it was pure fun. It wasn't perfect, but like you said Wagram it didnt deserve the hate it recieved by gamers. Gta5 can do plenty of things to improve the formula and immerse the player even more. Some ideas I have:
Add new terrain, such as a mountain range complete with snowboarding, lodges and skiing with a ski lift, everything you would expect to see on any popular pass. They can also add more rural areas and even a beach area that is much more lively. The forested areas need to include a wide range of wildlife and plant life as well. City live can use some refinement as well by adding even more every day activities to liven up the environment and adding more random dynamic events such as maybe getting a chance to witness an actual high speed chance, a mugging, other people picking up prostitutes and dropping them off, witnessing a pimp collect his money. We need to be able to actually walk into a bar and dance such as in ballad of gay tony, but be able to order drinks and pick which women we want to talk to, including all the activities you would normally see at a bar. Also add in random bar fights, bouncers throwing people out etc.
As for improving the storytelling, rockstar needs to give the player the ability to craft their character by allowing us to shape our own story and make more critical decisions, **SPOILER ALERT Kind of like in gta4 where you got to choose which person you wanted to take out in that specific mission with playboy and dwayne END SPOILER** accept allow for more crucial decisions that can alter the rest of the game in a serious way. Also add in destructible environments and justify these buildings being rebuilt by way of having an actual construction company come out to fix up the buildings. This can mean that cars can be driven into buildings and create openings, destructible objects. Also give every object in the game euphoria physics.
There need to be characters that you can permanently kill if they annoy you, just not the ones important to the story as killing people is too simple a task. Confrontations also need to be more personal and intense, not one dude taking on 50 but something in the vein of the bourne series where he is a specialized combat expert amongst other things with a seriously improved combat system instead of the awkward controls of gta4, including finishers and takedowns etc.
These are just some of the ideas that I have, and realize that implementing everything here probably wouldn't be worth it to rockstar but including these ideas and more would create one of the best games ever. Also transitions from cutscenes to actual gameplay need to be more smooth with much improved animations.