Multisite Question

Yes, Connections should be well suited for this. My only thought is that since each region will be a subsite seems kind of heavy and will be harder to maintain.

Here’s how I would do it on a single site.

Create a page for you directory home page, we’ll just it “Directory” for this example.
Input your entries, taking care to be consistent with the state names.
Now, using the Custom Link feature on the Menus admin page create the region menus using URL/s like so:
our-site.com/directory/cat/barbers/region/kansas
our-site.com/directory/cat/barbers/region/utah

The URL/s will automatically filter the list on the directory home page to be in the barber category in Kansas and Utah respectively.