I'm really glad the devs are working so hard on the "city experience". It's just the sort of oft-neglected, extra-mile feature that turns a good game into an extroardinary one.
Here are my most memorable video game cities:
Ascalon (Guild Wars)
It started out looking like your typical generic happy fantasy city, but then the Searing happened and the place got blasted so hard the entire kingdom turned into a barren wasteland. Green lawns and tan cobblestones were replaced by red rock with black scorch marks and the occasional shining crystal sitting at the bottom of a crater. Even the topography changed; there were a lot of moments where I said something to the effect of, "There used to be a cave here."
Kaineng (Guild Wars)
The main port city of the game's second chapter, and the first place foreign characters see. This was an asian-themed city whose slums sprawled across half a continent. It was notable mainly for three reasons: First, except for a few upscale regions it was almost entirely drab and ugly. Brown roofs, dirty hovels, gray streets. Second, it was laid out like a maze and was extremely difficult to navigate. Third, it was the first time players encountered normal city amenities like merchants and large groups of friendly NPCs outside of non-instanced outpost areas. Overall, I hated the place.
Horteka (Skies of Arcadia)
Mostly memorable for the music, but the unusual verticality of the area was interesting and fun to run around in.
Esperanza (Skies of Arcadia)
A poverty-stricken outpost long ago abandoned by the nation that built it. The rusty metal, blood-red skies, and cheap prefab architecture really reinforce the general atmosphere of despair.
Silent Hill (Silent Hill)
It looks like a normal town at first, but the everpresent fog makes streets and open spaces very frightening and claustrophobic. There are scary things out there, and you won't see them until they're right on top of you. Then there's the Otherworld, where the walls run with blood and you suddenly find yourself in an even scarier alternate version of the town. If that's not bad enough, they made a whole series of games based on this place. This is a town with some bad history, and you just know that anyone unfortunate enough to go there is likely to come home dead or worse.
Nist Akath (Dwarf Fortress)
This is a really good example of how to get a unique and memorable city in a sandbox game. Nist Akath started as a community game in the most inhospitable location imaginable: A haunted, barren, freezing glacier atop a multi-level aquifer. People said it wouldn't even last a year. Fast-forward a few decades, and it becomes the world's strongest fortress ruled by the most powerful mortal in all existence. Everyone who goes there either dies horribly or becomes an unstoppable badass. It is the most epic epic of epicness in all epic-ry. I think the key to its memorability is the combination of a distinctive local environment, a leader with a strong personality, and the fact that events within the city have a tendency to be strange, horrifying, totally awesome, or all of the above.
Continuing the absurd length of this post, I really like some of the ideas in here about how to make cities in a TBS more interesting and memorable.
Dagoth's idea of having a city's architecture reflect the local environment would help in ways that are functional as well as cosmetic. There have been times in GC2 or Civ4 where I've mistaken a particular city or arrangement of planets for a completely different place on the map, and gotten very confused as a result. Making cities visually distinct would help prevent this. However, the cities should still look like they belong to the same kingdom even though they use different materials or styles. That can be tricky to do, but I think the results would be worth it.
Erik's idea of giving newly-settled cities customization options interests me greatly. It lets you make cities more unique, and the more time you spend you designing something, the more you remember and appreciate it. It's interesting from a story perspective, too. It's not unreasonable to imagine a Sovereign sending a hand-picked military expedition to fortify a strategic location, or offering good mining equipment as part of an incentive package to encourage hardy citizens to populate a resource-rich mountain town.
I wouldn't leave it all up the player, though. Later events should also affect the city, and a small amount of unpredictability keeps things interesting. A city that is frequently attacked might have lower production, as citizens spend more time fortifying their homes. They could probably offer some of the best military training in the kingdom, though...
Having the game save the names and characteristics of legendary cities/battlefields/whatever for use in later map generation would be awesome.
Goodgame also mentioned having neutral cities on the map that you could interact with. I'm imagining sending a diplomat or spy unit to a neutral city full of cutthroats and mercenaries, and negotiating some "unofficial" action against my enemies. (Or allies!) There are a lot of interesting things you can do with non-aligned cities and forces; much more than GC2 ever did with Minor Civs.
Wow, there's so much you can do here. It's almost surprising that BoogieBac was the first one to ask this sort of question before.