Additional portfolio sorting options

Hi guys and congratulations on your amazing work!
I’ll get straight away to the scenario we want help with.

We have to present some professionals that offer some services (1 to 6 Services) and these professionals are based in different cities/areas (20 Cities).
We have used the portfolio Items to build our professionals pages – one portfolio item represents one professional.

Professionals can offer up to 6 services each (A, B, C, D, E and F).
One professional can offer ‘Service A’, ‘Service B’ and ‘Service D’
Another professional can offer ‘Service A’, ‘Service B’, ‘Service C’ and ‘Service F’
Another professional can offer ‘Service B’, ‘Service D’, ‘Service E’ and ‘Service F’
And so on…
We then use a Masonry Grid to display these professionals on the front of the website and the visitor can use the Masonry Grid Sort Options to find the professionals that offer the services he is interested in.

The problem is that because we have professionals in a number of cities we want to find a way to clear up things upfront.
If someone lives in, let’s say, New York City, it would be nice to have a way to first choose the city and then play around with the sort options. There is no point in him looking through all the professionals one-by-one in order to find who is operating in his city.

One way to do this, it would be to create the cities as main menu items (by using mega menu to display them in a tidy way).
Then we would have to build endless categories like ‘NY Service A’, ‘NY Service B’, ‘NY Service C’, … ‘Texas Service A’, ‘Texas Service B’, … ‘Utah Service A’ etc. So when someone clicks on NY on the menu he would be directed to a page with a Masonry Grid displaying all professionals with the aforementioned related categories attached to them.
That could be 6 Services x 20 Cities = 120 categories in order to properly show the list of professionals. Moreover, the sort options would display e.g. ‘NY Service A’, which looks funny and could also be very big. I don’t think this is the way to go.

Another way would be to create 6 Service Categories and 20 City Categories and then have a way to tell the Masonry Grid that: ‘You must display Professionals that belong in these 6 categories but are also in this particular city’.
In this case again we would use our main menu to navigate users to the relevant city page, where the Masonry Grid would only display the professionals in this specific city.
Optimally the city should not appear on the Masonry Grid Sort Options. It could be hidden someway.

We would be tremendously grateful if you could suggest or provide us with a solution.
I know very well that this could be way beyond your theme support scope and I will completely understand if the answer is: ‘Sorry, we cannot help you’.

But in case this is something that can be achieved that would be so great and very much appreciated. That is why I’m asking anyway. If we don’t ask, we’ll never know :)

Thank you again for your help and excellent product!
Take care