looking for…

I know what I want, but I don’t know how to describe it to the various search engines.
Maybe someone here will know what I am looking for and point me in the right direction?

I am looking for a plugin to allow two separate but searchable lists of categories.

The idea is to have users search by city and then, within those results, search by specific (and multiple, ie checkboxes) categories.

I can use the native WordPress categories for the latter part, but what do I use for the first part? And how can I make them searchable?

Maybe I need more than one plugin? I can’t even find one that will allow me to have separate lists of categories.

Also, this cannot be widget-only – I need to use it in the main body of the page.

Thanks!