How to let users choose where to search for posts?

Question

I have no code to let you correct/see, I'm still in 'thinking stage'. What i would like to achieve is this: A real estate website with a few search functionalities. This new agency (REALLY NEW we have no office actually!) will split the city in 4 (or more) parts, in each one of these part there will be different houses, each house will have different number of rooms or will be available only to girs/boys.

So the user when reach my website have to be able to choose:

Search Form 1

• Which Part of the city
  • Accept boy/girls/both
  • Budget

Search Form 2

• Accept boy/girls/both
  • Budget
  • Which part

And so on... Maybe the best way to have a simpler search query would be to use Custom Field, Am I wrong?

Is there anyone who can help me to find a tutorial, or can point me to the right direction or has/know a plugin to do something similar?