The first thing you need to change is the Map type. You're currently using a filled map. Go to show me (top right corner) > switch to a symbol map.
The second thing with geographical data is that they're better when organized in hierarchy. Like in the screenshot: Country / State / City. So that Tableau can know that this city belongs to this state in this Country.
To do that simply bring the country dimension (and the state one if you have it) in the mark card. It should work. Let me know if you still face issues.