Difference between categories and structures
Great question. Categories are used to organize a variety of content including entries, assets, even other categories. Categories themselves do not have content (besides maybe a description and key image), but can be related to content. They are a great way to group related entries together and provide a semantic structure (little s) to your content. 

Structures (big S) are entries. They are content. The biggest difference between Structure entries and Channel entries is that Structure entries can have children, parent, and sibling entries. Additionally, Structure entries should not be "date driven" like Channel entries would be (blogs, for example, are date driven).

If your content needs to be segmented by cities, and is in some way date sensitive, I would recommend setting up city Categories and have a Channel for your entries. Fortunately, Categories can also have parent, children, and siblings, so if you needed to organize your cities by state, you could accomplish that easily with Categories. This is why the category fieldtype does not let you reorder them.

For quick reference, check out the documentation on section types and categories.