Steven Zahm@ Larry
My sincerest apologies I missed replying to you!
Yes, all templates except market will work with any responsive theme. CSS conflict do happy but they are easily resolved when encountered.
The search is a simple keyword search which does search both the state and zip code fields by default. You can limit searching to just those fields in the settings for an adhoc region search. There is not a more advanced search like in your current setup, sorry.
I look at you data seems to suggest that Connections does include most of the fields you require however since there is no custom field support at this time anything that does not fit with the fields provided you would have to enter into either note or bio field. So depending how important that data is to the record Connections may or may not be a good fit for you needs. I suggest downloading and installing it and enter a field entries to get an idea if it will work for you. You can test the search and category filtering in the admin to get an idea of how it will work in the front end.
Again my apologies and I hope this helps you.