I’d say it’s quite a huge task to split the default taxonomy in two dropdowns. Maybe some wizard stumbles upon your question and enlighten us…
The biggest problem I see is the split itself, because you can modify the query &cat=1 to &cat=1,25 so as to list two categories (by their id’s).
What I suggest is creating a custom taxonomy for dealing with either Products or Services. And leave the other in the default categories.
And then apply the solution I linked in the comments to the question.
This way is easy to have two dropdowns and do the custom filtering you’re looking for.
Just tested and it works.
Hope this helps.