Category Layout Suggestions for Directory Website

Hello wordpress folks. I am about to undertake building the most data intensive wordpress site I have ever attempted.

I am having trouble wrapping my head around the best way to structure the categories/subcategories and was hoping someone with a bigger brain could make a good suggestion.

It will be a business directory covering all 50 states in the US and also be categorized by business type. I would like to make the site easy to search so that things don’t get buried as well. Folks should be able to search by state and business type, possibly even city.

So far I know I need 50 States as categories as well as 15-20 business types such as auto dealers, dentists, restaurants, bars, etc…

I was considering breaking it down by region as well: Northeast, Southeast, Northwest, Midwest, etc..

Just cannot decide how to most efficiently lay this out without making a big mess. For example:

Parent Category: Northeast
Child Category: NY
Grandchildren Categories: auto dealers, dentists, restaurants, bars

This looks ok but it would mean I would have to make new child/grandchild categories for each state. The reason for using the regions as top level categories is just to make it so that all 50 states don’t come out of one drop down menu!

It may be better to just have 50 states as top level categories, followed by 15-20 Business Types as top level categories. I also considered basing everything on tags, but that hurt my brain even more.

Any thoughts would be greatly appreciated.