I can envision something that works more like a dating site solving these problems. Both parties put in descriptions of themselves and criteria for what they're looking for in a potential employer/landlord or employee/tenant. Then the site matches people based on these criteria and sends both parties a list of good potential matches. Et voila -- a much smaller, more relevant set of data for both parties.
I know there are sites that already do something like this in one domain or the other, but I haven't seen any that really do a good job. I also think there's huge potential for putting the two problems together, since people are often looking for both a new job and a new apartment at once, and they use similar criteria (e.g., location, proximity to XYZ, seeking someone who has or wants XYZ...) that are currently difficult to search by.
Edit: I see that "dating site" and "Craigslist competitor" are both on the original ideas.html. I see my idea as an instance of these.