Changing the graphic is the least of the problems. Cities produce little food as it stands now, setting up a rural to be a city requires logic to replicate, removing food, adding gold. How do we decide by how much for each region for each possible state (base, town, stronghold city). Will we end up with realms founding and destroying cities to try and find those the the best stats in the best position (min/max issues)
The idea would be to start off with a few base region types, for example: Hills, Mountains, Plains, Badlands, and Wastelands. To which you can tack on a subtype, like forested or urban (could even add farmed). Then, the base stats would be determined by base region type, plus a subtype modifier. It could either be proportional to the region size, or, since they are mostly rather similar in size, all regions could simply be made equal. "Improvements", like strongholds or cities, can tack onto urban regions. To keep things simple, no need to make them produce less food, just make them consume more. After all, the city doesn't encompass the whole region.
Cities are destroyed and rebuilt regularly the time as it is, the only difference is that they don't change locations. As long as "moving" a city is costly and timely, I don't think we should obsess over min-maxing. Heck, along the same line, I'd also scrap the "no strategic capital move" rule, since it's poor intent-based rule and the only ones who get punished for it are those stupid enough to publicly admit they are acting out of strategic interest, plenty of other people having moved a capital along the border with no ill consequence. Just replace it with a scaled mechanic that gives greater unrest to a region when distance from the realm's capital is at least 25% greater than its distance to the centroid. Or if there's no code available to calculate the centroid, when the distance to the capital is greater than 2 standard deviations. Let people move around their cities and capitals as they like, just make it harmful to go full gamey.
Those who would benefit the most from this, I believe, would be the smallest realms with eccentric capitals. If allowing them to put their capital on the border helps them get involved and start wars, instead of being hidden far behind out of fear, then good for them.
I do think it'd be simpler to implement on a fresh continent, though.