I’ve thought about this a bit. I’ve previously played around with a three-tier category system and different tag-based navigation systems.
category: local nodes
tag: continent (need to be discussed if it makes sense)
subcategory: nation (nation shall be well visualized, that is why the continent is tag)
tag: city
I think you essentially need a tag dropdown specific to a tag_group, with the tag_group being determined by the category context (to accomodate different city groups for nation subcategories).
In terms of having maps in places other than a topic list, or embedded in a post, the Locations Plugin has a componentized map that can be inserted in a category page.
You could achieve both in a theme component. If you need help building such a component I can give you some pointers if you want to try yourself, or you could hire Pavilion to do it for you.