It should have the Continent>Country>Region(and/or State)>City hierarchy.

I've looked and found the usual suspects (see below) but they don't seem to be entirely accurate (at least the free versions).

If you've had experience with any databases like these, any advice would be greatly appreciated as to which is the most accurate/reliable.

https://www.maxmind.com/en/worldcities

https://developer.yahoo.com/geo/geoplanet/

http://www.geonames.org/export/

http://www.geobytes.com/FreeServices.htm

Also found a couple of discussions on Stackoeverflow:

http://stackoverflow.com/questions/2463004/free-sql-script-to-get-a-list-of-countries-provinces-states-and-their-cities

http://gis.stackexchange.com/questions/603/is-a-country-state-city-database-available

Also found some old post on HN:

https://news.ycombinator.com/item?id=1093005