Fake New Orleans as the main city, with Vice City off to one side and Fake Houston on the other.
Some desert, some backwoods, some swamps and bayous, three distinct metropolitan areas, and some small towns. Complicated winding road networks in some places, long flat stretches where you can burn along the highway in others. Airplanes would be a valuable way to get from one end of the map to the other, instead of just being a "something to do" feature.
Plenty of opportunity for local color unique to their areas. Cowboys, bikers, hillbillies, Creoles, Cajuns, Cubans, etc. Side missions with one clan could get you in trouble with another and change the way small parts of the story play out. Long haul trucking, smuggling via water routes, turf wars, police/vigilante/fugitive* missions... Completing a set of side missions for a particular group could provide resources like backup gangs, special equipment or vehicles, or whatever else.
Optional homesteads/headquarters in each of the three major regions. Not just places with garages where you save the game and change your clothes, but buildings/land where you can station crew to defend your territory when you aren't around, install meth labs or pot plantations or chop shops, and run management missions to keep your income levels up. (Plus expenses and bribery to have something to spend your money on other than buying and customizing your vehicles and other toys.)
*In my mind, a fugitive mission differs from a vigilante mission. You don't just follow the red dot on the map and kill them, you have to really search, and if you don't read up on the target and figure out what kind of places they're likely to be, you won't find them.