Force redirect if a valid taxonomy term is not at the start of the URL?
I wouldn't recommend using such system because I also have the gut feeling that this would create some major confusion for modules relying on the drupal path system.

I think you should better deal with subdomains like city.site.com.