Adding to Daniel's comment, I'd say the big difference "...through our faceted search." It's important to have both the XML entries and a crawl path. An XML sitemap may be enough to get the pages indexed, but they won't inherit any internal link-juice. That comes through your internal links. Somewhere, there needs to be a link that Google can crawl to the other cities.

The direct back-links will help, and should get you indexed and possibly ranking, but you're still losing the authority from the domain as a whole that you'd inherit via internal links. The upshot is that you'll lose ranking power.

They shouldn't - a META NOINDEX is easier to undo than a Robots.txt block, 301, or canonical tag, in my experience. The biggest risk is just a delay - it may take Google a little time to re-index the content once you remove the tag.

What I wouldn't do is add/remove the tag rapidly. For example, if you had a product that went out of stock every other day, I'd leave it alone - Google wouldn't respond quickly enough to all those changes. So, once a category has enough results, I'd lift the NOINDEX permanently. It's really just a move to consolidate while you build up the site - both in terms of content and your link profile.

Unfortunately, the painful reality, especially if you've been hit by Panda, is that you probably can't support that scale or that it looks thin to Google. 500 cities X 50 categories = 25,000 "category" pages, so to speak, all of which are basically just search results. For most sites, it's just too much.

I'd definitely keep the cities as sub-folders. If you go the sub-domain route, you could fracture your internal link-juice even more. It depends a bit on the authority and marketing budget of the site. If each city is a separate property with its own sales force, budget, etc., there may be a logic to sub-domains. Unless you're Groupon or someone like that, though, it's probably a bad idea.

You may have to prune down the indexed content, to be frank. I'd look for other Panda factors, too, like aggressive ad density (too many ads to too little content) or very thin pages. If you have tons of cities or categories with no listings, META NOINDEX them. You could even do it dynamically - only let Google index a page if it has 1+ listings, for example.

I'd also take a look at other low-value content, like paginated search. If each city has 100s of pages and you're indexing page 2, page 3, etc., consider consolidating them. It's a tricky topic, but Adam Audette has a great write-up here:

http://searchengineland.com/five-step-strategy-for-solving-seo-pagination-problems-95494

These pages can look very low-value to Google. Add in search sorts and other variants, and your 25K categories could be exploding into hundreds of thousands of pages, before Google even gets to the listings themselves. The ads are the real meat of the site, and that's where you want Google to focus.