There are many government types to choose from.
Assuming whatever race(s) we choose is/are somewhat similar to human beings, Tribes should be the smallest social structures (apart from family units). Tribes are smaller societies within a given culture, mostly led by a chieftain or a council of elders. They oftentimes either live of the land, nomadically or otherwise, and/or raid neighboring nations/tribes. While they are much more mobile than settled cultures, they do tend to confine to one general area.
(See: the Sioux, the Celts)
City-states, like the name implies, are what you get when the Tribes stop banding around and form a village. Eventually, that village will grow into a city and voila! A City-State.
City-States are in general more stereotypically "civilized" than Tribes. Here's the point where you'll usually start finding stuff like writing, taxes, wars for conquest (rather than simple raiding), and other signs of civilization.
Like Tribes, citizens of a City-States usually share the same language, law, religion, etc. but usually in a much more formal manner. Expect more centralization and written law.
(see: Sparta, the Vatican)
A nation is an entity that consists of many cities and encompasses a large area with (somewhat) defined borders. Nations are usually fairly homogeneous, and claims to be the sole legitimate authority of whatever culture it represents and has as a goal to include all of it within its borders.
A Nation is usually built on a sense of nationalism and works in opposition to other Nations. Typical signs of a nation is covering a large area within defined borders, a centralized government, and a complex administration.
(see: most countries today)
Empires are the largest political entities there is and, contrary to earlier ones, encompasses more than one culture. Empires are heterogenous (it's a word!) but forces their rule on their subject peoples. All power usually lays in the hands of one or a small group of individuals. Mostly very centralized and with a strong military.
(see: Rome, Ancient China)
Monarchy (Kingdoms, Khanates, Sultanates, Chiefdoms, etc.) is a form of government in which all power, either literally or ceremonially, is concentrated within one person meant to represent his people(s). Usually hereditary, a line of monarchs forms a dynasty.
(see: Great Britan, Saudi Arabia)
A Republic is a state in which politics is considered a public matter, and citizens are encouraged to take part of. Usually adheres to some form of democracy, either direct or representative, in which case the state is lead by a single or group of persons voted in by the people. Not a hereditary form of government.
A Theocracy is a state that is ruled by God (or gods, as it were), usually through a priesthood (but not always, if we include fantasy realms). God, or his representative, is the ultimate authority on law, morality, or anything.
If the rulers are mages, it's called a Magocracy.
(see: the Vatican, Mallorea)
There are of course many variations of these and even more forms of government! Merchant Republics, Military Juntas, Technocracies, etc.