Thank you dave! that was the answer I was looking for. Got it in a round about way but still got it.

I'd be delivering a sitemap of pages that google could see everything the user could see in a targeted format. The targeted format (the search) was the part I couldn't get google to see easily.
I do appreciate everyone's feedback, even about the zip codes. When we get closer to launching the site I'll make a followup so everyone can see how it turned out and maybe some of you will see that the zip code based search is a good idea. Then again, you may not. I am going to take into consideration some things that I had not prior to this (sparsely populated areas, etc).
I have given it more thought and I think from what I have gathered I will be doing a drill down by state right from the initial release, which will list all information pages for providers in that state as a way for users to see if their favorite provider is listed or provides the niche service we are targeting. Then I may look into more radial searches (still based on zip codes) since I already have that programming in place for the providers to find the zip codes they want to target. I could go into great details about why one suggestion or another is not optimal for the site, but that wasn't the real subject anyhow.
Thanks again everyone!