Since Civ4 has less cities to build than Civ3, and that we will get more detail orientation on the career development of units, I suggest the following:
City Names. Name based jointly on geography (prefix or suffix), with the core name based on a combination of resources available, topograpy and finally what cultura/religious/scientific/civic development that took place there.
The civs name should reflect a history everyone can relate to.
Captured cities: Here we should apply the honorary citizen system, which is for citizens that made a major impact for securing that city. We can also change our original names, if someone wants to honor a citizen in a peaceful period.
For units, we should follow the citizens list for the sake of simplicity, we can be quite certain that we will use up all our names, sooner or later in this fashion.