Show posts from two categories using a search facility

I’d like to have a search facility for the user to show the posts using two drop down boxes, one with ‘category’ and one with ‘city’. So the user can select posts within both e.g. ‘web designer’ in ‘exeter’.

I’ve tried a few search plugins but they don’t seem to be quite what I’m looking for as they’re searching content within a post; I want to just show the posts that are in both categories.

Any ideas most gratefully received as beginning to tear my hair out over this!