Mayor of NYC is probably a better executive experience that many (most?) state governorships. Bloomberg isn't my cup of tea, politically, but he's certainly qualified to run if he decides to do it.
No, NYC is not a cross section of the US, but neither is Arkansas, and of the two, I'd say NYC gets closer to more of the population.
Absolute number of people is not the determining factor in any of this, but with no major cities in Arkansas, I reject the notion that Bill Clinton's governorship gave him experience with urban issues.