Free dataset of world cities, including geometry

If you're really talking about cities down to 500-1000 inhabitants, you can't even get that data if you pay for it. Even the locations of cities with 1000 people are something that's hard to pay for -- there's a lot of cities of that size in the world.

Commercial providers like NAVTEQ don't tend to have polygons for anything that small, for example, because it can't be collected via on-the-ground data.

If you limited yourself to looking for rough outlines of cities of 1 million people or more, VMap0 might have the data you're looking for -- but it's very coarse.

If you don't care about 'free as in freedom' but instead only free as in "I don't have to pay for it", you might try Reverse Geocoding; use a reverse geocoder to look up a location, and then look at the city field. This is probably your best bet -- but ties you to someone who has a good geocoder that they make available (Google) and all that that entails.