Well, it depends on what kind of city it is too.
Colonial cities, countries and states (i.e. America, Australia, South America, etc.) are usually named after
a) An Existing City (New York, New Jersey, Perth, etc.)
b) An Existing Native Name (Mexico, Wagga Wagga, Oklahoma, Minnesota, etc.)
c) (most often) Some famous person or explorer or saint (Sydney, Melbourne, Washington, Bolivia, Sao Paulo)
So... go to the library, or somewhere where there's lots of books,
Write down as many different and interesting last names as possible,
Look up a book of saints or famous historical figures, there's always good names there!
Find an atlas and look up existing place names,
And find some foreign language dictionaries and find words there!
Voila!