In a fantasy world, the government could be practically anything you want. You just need the appropriate reasons to justify it.
However, there are two things you have to take into account when choosing your system of government:
- Population: 10,000 is a fairly low population level. Looking at historical examples, Classical Athens had at least 10 times that. The Republic of Venice had a population of about 180.000 in 1490 and the Republic of Ragusa had 30.000 inhabitants in 1808. Population is, usually, on par with govern complexity. Not the same level of complexity, bureaucracy or institutions are needed to rule a city of 10,000 or a city of 180,000.
- History, beliefs & economy: Systems evolve for a reason. The beliefs of the people of your world and its past history would have shaped their current form of government: why they're city-states and not kingdoms, republics and not a monarchies, for example. Or their form of government may have changed over time. Also, a city with a agrarian-based economy or a city with a commerce-based economy may have different forms of government due to the different interests of its citizens.
That said, let's take a look at some government options.
Democracy: Classic Athens
Classical Athens is a most well-known example of ancient democracy. However, it was not the kind of democracy we know today.
To start with, only adult males could vote. They were about 10% to 20% of the total population. Women, men with suspended rights, slaves and foreigners were not allowed to vote. It was also a direct democracy system. Any male with the right to vote had the duty to go to the assembly and vote. Vote could not be delegated.
Most officials were chosen by lots among those who nominated themselves, and magistrates held office for a year. Of course, not anybody could afford to nominate themselves. The full system was a bit more complicated, including councils and tribunals.
In you world:
Fitting a Athenian-like type of democracy with the class system you mention would be easy. Just limit those who can vote with something like censitary suffrage, which basically means that only those who hold a minimum amount of money or land could vote.
Mixed system: Sparta
Another Greek example is Sparta. It was a mixed government system governed by a system of laws.
Sparta was ruled by two hereditary kings supposedly descendants of Heracles, with religious, judicial and military duties. The existence of the dual monarchy had usually legendary explanations.
They were not autocratic rulers. The Gerousia, the council of Elders, made up of 28 men over 60 and the two kings, made the decisions of high state policy. The Ephors shared the executive branch of government with the kings. The Apella was the assembly of citizens, that only could decide between the alternatives presented to them.
Oligarchies: Italian city-states
Until the end of the 18th century, there existed several city-states Republics in Italy and the Dalmatian coast. Though officially called "Republics", their governments were, in fact, oligarchies, with the power in the hands of a chosen few.
Venice is, perhaps, the best-known example. The Doge was the ruler of Venice, were elected for life by the city's aristocracy (of which the Dogo was also one) though a council of 40 members.
Early Doges were autocratic rulers (they held all the power), but their powers were later limited and shared with the Great Council, composed by members of the patrician families. With time, the Doge's power was limited again by the establishment of the Minor Council, with the power shifting mostly to the Council. There were also checks put on it to prevent the development of an hereditary monarchy.
The Doge also had a ritual role, symbolizing the marriage of the city with the sea (Venice was, after all, a thalassocracy).
Other examples: Republic of Genoa (1005-1797), Republic of Florence (1115-1532), Republic of Ragusa (1358-1808).
Autocracies: Monarchies/Principalities/Duchies/etc.
A city-state the size you propose could easily be ruled by a single ruler, that could be a (Sovereign) Prince or even a King. Other titles historically used were Grand Prince, Grand Duke, Count, Margrave, Landgrave, Count Palatine or even just Lord. You could also have a dual rule, a diarchy, with two kings, princes (see Andorra) or a prince and a religious leader (see Tibet).
Phoenician city-states were ruled by Kings. Principalities existed in Medieval and Modern Europe. Liechtenstein, Monaco and Andorra are the only surviving ones nowadays, with Luxembourg being a sovereign grand-duchy.
The lordship could be either hereditary or elective, where the king/prince/lord is usually chosen by a council of nobles or, in other cases, by the army. It can also be a mix of the two, with the council choosing from the members of a single family (for example, between the children of the previous ruler), or provisions may be put in place to prevent a single family from holding successive kingships.
Dukes and Counts also ruled independent territories in the Middle Ages. For example, the Catalan counties that broke off Charlemagne's empire or the Duchy of Milan.
In your world:
A Prince may also be vassal of a king while remaining sovereign (see the history of Monaco). That option could work with the cities near a kingdom you mention. These cities could be sovereign, but required, for example, to pay some kind of tribute or have their foreign policy supervised or curtailed.
If religion has an important role in your world, the ruler of your city could easily be the High Priest(ess)/Pope, etc, ruling by "divine mandate".
The Papal States were a real-life theocratic elective monarchy and so it's the Vatican City nowadays.
The bottom line
The best system of government is the one that best fits the world you've created, whatever it has a real-world equivalent or not.