That depends on what sort of setting you're trying to model. A lot of fantasy realms are pretty underpopulated. The Shire is around 50,000-100,000 people, and Gondor (the largest realm in Middle Earth, is around 1 million.
Historically, a large city in Mesopotamia around the "dawn of civilization' was 30,000 people or so. You don't get cities of 1 million or more until the turn of the common era - Rome in the 1st century CE, Baghdad in the 8th, and China had a bunch in the 11th/12th century.
As far as kingdoms go, again, it depends. One historical model stipulates that a realm that defines itself as the entire world - i.e. something like Christendom, dar al Islam, the Hellenistic World, the Middle Kingdom - takes around 60 days to traverse from one end to the other (not at top speed, but if you're transporting goods, for example). Individual kingdoms, duchies, territories in this space are going to be significantly smaller, depending on how many the realm is broken up into.
One thing that has started to irk me lately: when people design a world, they start modeling it as if it were another planet, so there are oceans, continents, etc. My problem with this is: how many people in your world think of it as a planet? How many people in that world know about the existence of other continents? If the answer to these questions is "zero" or something close to it, design something that you can actually use right off the bat (a kingdom, realm, may one continent), and worry about the rest later. If there are no planetary maps in your world, the players will never see the one you make anyway. So make something that tells you relative distances and locations of terrains, cities, castles, etc., and fill in the blanks later. Remember also that travel can be very unsafe precisely because there are no maps, and the chances of getting lost are pretty high (if you have no ranger, that is).