The City itself
Let's assume we have a city of the size of the Peloponnese (round about 22'000 square kilometers) which is very dense populated (by medieval terms) and is isolated from the rest of the world (think of something like an ocean surrounding the island). The city wasn't 'planned', it just grew bigger and bigger so the city layout itself is a bit flawed (e.g. bad street layout). Let's for simplicity assume there is enough food for (nearly) everyone.
The Population
All citizens use the same common language, although many dialects do exist. Nevertheless it's a multi-ethnic population with different religions an different customs. Sometimes the tension between these different culture groups leads to nasty crimes but all in all the situation could be considered as stable. Wealth is distributed pretty bad (as usual) but there is no particular cultural group having a much greater share of wealth than the others.
The Government
Now that’s the questions. I'd like to have a central ruler sitting right in the middle of the city. Given the size of the city, a direct rule however is deemed to be impossible. Therefore, a greater deal of decentralization appears to be required.
Ideas so far
Feudalism
This is the first thing I had in mind: Have a single king with multiple vassals, which in return have multiple vassals themselves. You get a high decentralization with an acceptable control from the central government/ruler and you get a decent degree of stability. Feudalism also allows for some interesting storylines regarding counts, bloodlines and similar stuff. There are some fatal problems though...
Feudalism was built on an agricultural society. The lower vassals had a large mass of peasants beneath them. Feeding people was hard so agricultural land was expensive.
Feudalism needed a constant change in borders. The liege gave its vassals land in return for favors or good work which the vassals children inherited on death. Works fine until you got no more land to distribute. I'd like to dispose the idea of the civil war emerging every 100 years because the vassals get greedy for more land or the idea of extreme balkanization of the city until every citizen is a landlord himself.
'Mayorism'
This approach features more bureaucrats and fewer nobles. Each district has a mayor and a smaller council designated to govern the pile of land he's been assigned with. A mayor is not of noble blood but excels in administrative skills. Each mayor may rule until death, after which he is replaced by any other administrative professional from anywhere, or until another person has been assigned to do his job (because the former mayor was incompetent, corrupt or....). There are no elections for the mayor as we don't want the citizens to get a taste of democracy and get uppity against the crown-authority. Up to this point the system would prove pretty stable, but here are some problems:
The king most likely has better things to do then to assign each of his thousands of mayors day to day anew. Like in feudalism he'd install multiple layers of administration, that in the end a group of let's say 10 people assign the jobs for him. This would then lead to a concentration of power in the hands of very few people which in return could get come to the conclusion a council of ten people is better than a single king.
Bureaucracy was on the rise late 17th or early 18th century which is clearly not an option for a medieval based setting. Writers in ancient Egypt did a similar job and different empires had different people doing the same job too, but all of them used a more or less centralized approach. Using common people for administrative jobs became fancy after bourgeoisie was on the rise and enlightenment was more widely accepted.
EDIT
As there were many question regarding the city. First of all, it’s a fantasy setting. The size is absurd, but that’s what it’s all about and that’s why it’s interesting in the first place. No some answers:
Underground caverns/tunnels
Get yourself some underground cave system with some tasty mushrooms and some solid building material to mine. If you’d go crazy you could use your poo to fertilize the mushrooms and build underground farms etc. but I’d rather like to keep the details out of here. Just dig down, eat mushroom and be happy. One could also dispose corps into catacombs. The risk of plagues a heavy disease is still high, but on the other hand side a city of that size probably won’t be a nice place in the first place. Constant mining may also lead to parts of the city to collapse into the depths below, requiring the city to be constantly being renewed.
Outer world
The city is isolated because there is virtually nothing out there. Total wasteland, nuclear fallout, giant metal dome, isolated island – you know what I mean. Nobody wants to go outside, because there is nothing to go to.
How to maintain order
Having a high revolt risk and a high population density some nasty uprisings should be pretty common. But then again it’s not utopia. The ruler keeps an entire army to keep his citizens ‘happy’. In other words were maintaining order with shock and awe. No bad intention here from the ruler, but the alternative is anarchy which is probably a lot worse
How to communicate
This is a problem for sure. Even if you’d use a mounted express line as suggested (which is exactly what I was planning to do), getting through the crowds will prove rather difficult, even if the horsemen were ruthless and wouldn’t care about the citizens surrounding them. An alternative for must-receive-immediate messages are carrier pigeons. However getting a message delivered in a matter of hours shouldn’t be as important as getting the message in a reasonable time. Sending messages in the middle age took it’s time too. In fact, waiting for messages was most common for that time. Governors would need to be able to take care of themselves (and their realm) without getting orders constantly from the central government.