One defect in CIV3 is the use of a single colour to distinguish each civ on the map. This made it unwieldy when there were 16 civs on a map. The colour differences between some CIVs was rather subtle.
To fix this, each civ should have 2 colours, not 1. With 2 colour patches, fewer distinct colours are needed to distinguish the civs. These colours would be a main colour (large colour patch) and a highlight colour (small colour patch). For example, the shield of a Spearman could have a device on it such as a cross, and the cross is the highlight colour and the field (background) of the shield is the main colour.
On all units, the main colour should take up at least 2 or 3 times the area of the highlight colour on the unit graphic. This allows the same colour pairing to be used twice and be distinguishable.
If this is implemented, 16 civs can have distinguishable colouring using just four colours (e.g.: black, white, blue, yellow).
On the map, the civs are coloured in patterns such as thick and thin stripes in the 2 colours, etc.
These colours should be configurable in-game, so that a player can choose colours for civs without needing to edit a BIC file. These colour settings should be stored in an INI file, so everyone can have their own personalised settings that are independent of BIC files or individual save games.
This idea will help out colourblind people, and also make it easier to tell civs apart for everyone.
None, Sedentary, Roving, Restless, Raging ... damn, is that all? Where's the "massive waves of barbarians that can wipe out your civilisation" setting?