Is there a free download of countries and their major cities available?
galleypage: You could use MONDIAL.
http://www.dbis.informatik.uni-goettingen.de/Mondial/The database is pretty extensive, but you should only need to query it once to get what you need.