You have it right. See if these help you nail it down:
http://thereforei.am/2011/10/28/advanced-taxonomy-queries-with-pretty-urls/ (the middle bit)
http://wordpress.org/support/topic/search-form-with-custom-taxonomy-dropdown
You may want to do something like getting all of the specialties of only the doctors at that particular location instead of displaying unavailable specialties and bumming people out! this should get you close. http://wordpress.stackexchange.com/a/125374
