Well... I prefer choosing your Traits+UU before the game, because I think they should be kept as 'Combos' so that All possible combos of traits+UUs and UBs don't have to be balanced.
To correct Firaxis' history deficit, the best solution would be to allow you to
1. pick your 'Trait+UU+UB' Combo... already done
2. Pick what your Civ+Leader will be Called... already done
3. Pick your City List, UU Name, UB Name, Banner, and Leader Portrait (The City List could be for Many more civs than a 'Trait+UU+UB' Combo is done for)
.. a place for all the Canada, Confederate, and Croatian civs... so that you can play them just by putting them on top of someone else.
Attacking Shipping..and other trade routes... should definitely be key. (even just a much wider range for ships to 'blockade')
I think a key change would be in some degree of civil war.. much larger than in Civ1 so that any City at any time can potentially consider breaking off (although it would be preventable by appeasing them.)
A game where you worried just as much about your own cities as your enemies.
This Should connect to Diplomacy (As your relationships with cities will be slightly more like that to Vassal States).. and would connect to the UN, which would allow the goal of essentially making all the civs into one (the same way as you keep all your cities and Vassals and Protectorates in one empire)... as well as many other ways.
Perhaps Civ4:Rebellion (or Civ4:Liberation)