This is a tough question because we don't know the business objectives of the company or site. If it's one company and you are trying to get local listing, why not just get a Google + page and verify all your local pages via the post card Google sends through the mail.
If all locations sell different things (car parts vs women shoes), new domain or sub-domain. But if your client is selling the same thing like Starbucks, then example.com/city.
I would personally create a page with schema.org markup for addresses and link them to /city