To add to Corey's response, I'll repeat what I just provided another question here on Pro Q&A.  Sitemap.xml files can handle a maximum of 50,000 URLs, however I've seen them choke with as few as 10,000.  Its important to run them through a tool like tools.pingdom.com to ensure they load within just a couple seconds.

Then submit them through Google/Bing webmaster systems and then see if they succeed in crawling all of them.

It's really a process of experimenting over time to find out the method that results in the most URLs indexed that in turn brings the most relevant traffic.  Personally I wouldn't have one for each category, yet without tests there's no conclusive reasoning either way.

If I understand your question correctly, you literally have duplicate content across the entire list of locations ("just the city variable changes on the page.").

If that's correct understanding, the best solution is to ensure that you have enough unique content for each location so list to ensure a comparison of location to location shows enough unique content compared to duplicate content.

Alternately, you would need to find a way to combine the least important locations into a smaller number of pages but the more locations you try to optimize a single page for, the more difficult the work becomes.