A great feature would be dynamic dropdown population based on previous choices.
Say the first dropdown was a taxonomy of animal, and this taxonomy contained the terms, dog, fish, cat
A second taxonomy might be product type with the terms, food, drugs, underwater castles
Say a post is with the terms dog and food. If selecting dog from the first dropdown and food from the second, great, the query returns the post. Now say we select dog from the first dropdown and underwater castles from the second, we get an empty result as their are no posts with both terms, dog and underwater castle.
If the second dropdown was dynamically populated based on the choice in the first dropdown then you would only ever be able to select a combination that actually returns a result.
You could choose which taxonomies to include, and then select which ones are to be dynamically populated, obviously you would not be able to dynamically populate the first. The dropdowns that are to be dynamically populated could be disabled or hidden until a previous choice is made.
The search button could be disabled until you have selected from the first dropdown. If the second dropdown does not become enabled this makes it clear there are no terms in the second taxonomy and you can just search using the first. If the second taxonomy does have a term.
Another cool way to do it would be kind of the reverse. If a term exists in the first dropdown that does not share a post with a term from the second dropdown, the term in not added to the first dropdown, making it impossible to make a select but be left with the second dropdown being grayed out.