My preference for what you're trying to do would be taxonomy for the following reasons:
SEO and User Friendly URLs
With categories and tags, WordPress permalinks are setup to put that information in the URL for you. This will go a long way towards the SEO and usability of your site because you'll be able to create URLs like:
http://yoursite.com/rentals
http://yoursite.com/for-sale/two-bedroom/123-fake-street
Hierarchy
I don't know if you have the need for it, but building a hierarchy with categories is easy. This will give you lots of flexibility when it comes to organizing your posts.
Theme Coding
As you said, it's possible to perform custom queries for meta data, but WordPress has many out-of-the-box functions to query and display based on tags and categories. This will mean that you'll have to write less code to get your theme to do what you want.