I will answer your second question regarding Overpass API. You can query cities for a particular country using that API. Just to demonstrate its capabilities, there is a web-based query tool for OSM called Overpass Turbo (http://overpass-turbo.eu) where you can submit queries and display and download data. The following query will provide all cities in the United States, for example:
{{geocodeArea:"United States"}}->.searchArea;
(
node["place"="city"](area.searchArea);
);
out body;
>;
out skel qt;
The query will return the following:
Per OSM Wiki, the "city" tag is used "to identify the largest settlement or settlements within a territory, including national, state, and provincial capitals, and other major conurbations." On the same Wiki page, there is a note about differentiating between cities and towns. In the above query, "city" can be replaced with "town". Other possible values (including country and state) are listed here: https://wiki.openstreetmap.org/wiki/Key:place#Values
If you are looking to obtain city-to-state relationships from the data, you may not always get reliable results. For example, you may get the following detailed GeoJSON entry for Duluth, MN:
{
"type": "Feature",
"properties": {
"@id": "node/19188464",
"is_in": "Minnesota USA",
"is_in:continent": "North America",
"is_in:country": "USA",
"is_in:country_code": "US",
"is_in:state": "Minnesota",
"name": "Duluth",
"name:ja": "ダルース",
"name:oj": "Onigamiinsing",
"name:ru": "Дулут",
"place": "city",
"population": "86265",
"population:source": "2010",
"wikidata": "Q485708",
"wikipedia": "en:Duluth, Minnesota"
},
"geometry": {
"type": "Point",
"coordinates": [
-92.1251218,
46.7729322
]
},
"id": "node/19188464"
},
but only the following entry for Madison, WI:
{
"type": "Feature",
"properties": {
"@id": "node/29941752",
"alt_name:ru": "ÐœÑдиÑон",
"capital": "4",
"is_in:continent": "North America",
"is_in:country": "USA",
"name": "Madison",
"name:en": "Madison",
"name:pl": "Madison",
"name:ru": "МадиÑон",
"name:ta": "மேடிசனà¯",
"name:uk": "МедіÑон",
"place": "city",
"population": "243344",
"state_capital": "yes",
"website": "http://www.cityofmadison.com/",
"wikidata": "Q43788",
"wikipedia": "en:Madison, Wisconsin"
},
"geometry": {
"type": "Point",
"coordinates": [
-89.3837613,
43.074761
]
},
"id": "node/29941752"
},