I always re-name my cities. In Earth maps, I try for geographically correct regional names like Labador, Dakota or Texas. This helps me find the damned things later in the game when a message pops up like "enemy spotted near..." Using regions, states or provinces avoids city-name conflicts with other civs.
In games on fictional maps, I generally have geograph "themes". My capital is always "Brooklyn", and nearby cities are Brooklyn neighborhoods like Flatbush, Bay Ridge, Red Hook, etc. If I settle a new area, I pick a new theme: names of my children and grandchildren, dearly departed pets, sports teams.
I always re-name captured cities, because the AI will sometimes build a new Aachen or Nottingham. I try for names that reflect the culture of the evicted civilization, such as "Fort Kaiser" or "Cromwell Heights".
What's important to me is finding the city in a hurry on a Huge map because I like huge maps, so my names are seldom totally whimsical, but themed.