The categories "city state", "kingdom" and "empire" are somewhat arbitrary, and depend (1) on what the state called itself and (2) on how it was categorized by later historians.
Let's look first at empires.
The archetypal empire was of course the Roman Empire. In Roman Latin, Imperium Romanum simply means "Roman power"; it was the expression used to designate not the state, but the territory over which Roman power prevailed. The state was res publica populi Romani, the common-wealth of the Roman people; the person whom we call "emperor" was, from a purely legal point of view, just another citizen who happened to occupy three key positions: he was princeps Senatûs (speaker of the Senate, thus having legislative initiative), he had tribunicia potestas majus (great power of a tribune of the people, so that he could veto any bill he didn't like and his person was inviolable), and he was imperator (commander in chief of the army). Of those, the most important was his position as perpetual tribune of the people, and when we say that for example Trajan became emperor on 27 January 98 CE, what we mean is that at that date the Senate gave him the perpetual and greater power of a tribune of the people. It was only in the late 3rd century CE, under Diocletian, that the position of an "emperor" became a legal reality and the emperor stopped being just another citizen and became officially the supreme ruler of the state.
In the early Middle Ages there was only one emperor in Christendom, namely the emperor in Constantinople. The title was revived in the West for Charlemagne by Pope Leo III in 799 CE; at that time the pope had a spot of trouble with the populace of Rome and, as he was seeking the favor of the king of the Franks, had the bright idea of bestowing upon him a title equivalent to the basileus in Constantinople. From that point onward there was one emperor in the west and one in the east; when Constantinople fell to the Ottomans in 1453, the ruler of the Ottomans inherited the designation emperor in the eyes of western Europe.
Sometimes rulers titled themselves emperors to make a political statement; for example, the Grand Duke Ivan IV "the Terrible" of Moscow titled himself emperor ("tsar" in Russian, from Cesar) to make it clear that he saw his state as the legitimate heir of the Christian empire of Constantinople. Sometimes rulers simply took the title emperor simply because it was more prestigious than a mere king (and was higher in the medieval order of precedence); for example, there was nothing particularly imperial about the Empire of Germany or the Empire of Japan, which were ordinary nation-states, at least in the beginning. Only in the later phases of existence of those states did they try to build actual empires—and they both failed spectacularly. Sometimes the empire in question was not even a state; for example, the British Empire was not a state in any meaningful sense, the various components having different laws, different currencies and verious degrees of international recognition. The British monarchs were not emperors of the British Empire, they were kings of queens of the United Kingdom and their various dominions, and emperors or empresses of India. Sometimes we call a state an empire because it was large and multi-ethnic; the best example is the Chinese Empire. Or we use the word emperor as the best way to translate a native title; for example, the emperor of Persia was actually shâhân shâh, king of kings, but emperor is more easily understood.
A kingdom is simply a monarchical state ruled by a king. Not all monarchies are kingdoms; in the Middle Ages there was an order or precedence, with the position of emperor as the most prestigious, then king, then prince, then grand duke, then duke, etc. Some states were kingdoms, some were principalities, some were grand duchies, some were duchies etc. depending on where in that order of precedence they stood. Sometimes a ruler was king in his country, but a mere prince or duke in foreign relations, for example Frederick William I of Prussia (the father of Frederick the Great) was king in Prussia, but elector of Brandenburg elsewhere.
City-states are easier. A state is said to be a city state if it is or was small, and it calls or called itself a city. Athens, Corinth and Sparta called themselves cities, poleis, so they are city-states, although Sparta ruled over a reasonably large territory and at one point Athens had a rudimentary empire. The Free Hanseatic cities of Bremen and Hamburg are city-states within the German federation. Singapore is a city-state in Asia.
A state is called an empire because:
- It calls (or called) itself an empire; example: Japan, French Empire (1st and 2nd), German Empire, Roman empire (from the 4 century onward).
- In the case of states no longer in existence: it was large and multi-ethnic; examples: Roman empire, Chinese empire, Russian empire.
- Quite often the two reasons co-exist.
Some structures called empires were not actually states; examples: British Empire, Holy Roman Empire. They are called empires because they called themselves empires.
The actual powers of the emperor varied widely; the elected emperor of the HRE had little direct power, whereas the self-made Napoleon I, Emperor of French, was essentially all-powerful.
A state is called a kingdom if it calls or called itself a kingdom, or the best translation for the foreign title of the ruler of that state is "king".
Sometimes we use different translations, such as prince or duke, or use the foreign title as such--tyrant, pharaoh, voyvode, maharaja, sultan, khan.
Some monarchies use lesser titles--Principality, Grand Duchy, Duchy, etc. In particular, most of the states which made up the HRE were not called kingdoms. For example, the Grand Duchy of Luxemburg, the Duchy of Bavaria, the Margraviate of Brandenburg (a margave is the ruler of a border duchy), the Landgraviate of Thüringen, the Palatinate of Burgundy, the County of Jülich; in fact, for a long time the only Kingdom in the HRE was the Kingdom of Bohemia; only later was Austria elevate from Duchy to Kingdom.
A city-state is a small state which (usually) calls itself a city.