NOTE I'm not a lawyer and this is only a suggestion, please do consult a professional.
I've been in your shoes before, If you're willing to compromise precision for the sake of completeness in terms of the number of businesses, I would suggest scraping yellow pages and/or sites like yelp.
There has been a long debate over the legality of this type of data scraping, and it seems to be in a gray area more towards being legal. Then again you should definitely see a lawyer for more info on that.
In my opinion the best method would be to use many sources and try to consolidate them using internal and/or external standards. For example, you can get a very sound dataset from yellow pages focused on small businesses, and some data on public businesses from NASDAQ (as mentioned in one of the answers) and try to normalize them for your own use.
Data/information seems to be very contextual and you usually have to do some mass operation on your datasets, why not use different sources while you're at it?