Unfortunately, other than being 99% sure there was an algorithm update around May 9th (dubbed "Phantom" by some folks), and even having seen it hit a former client, we have very few clues about what it actually did. Some folks have suggested it was "Panda-like" in which case thin content could be a culprit.
It's really tough to tell without seeing the site and the scope of the problem, but doubling up all of your rental pages could absolutely create problems, especially when you pair that with geographic searches and drill-downs. A couple of things I'd dig into before you completely change your structure:
(1) What's the scope of the doubling up, relative to your entire index size?
(2) Are there other culprits, such as search sorts and filters in play?
(3) Have you managed pagination (most likely with rel=prev/next, but there are other options)? With all of these geographic folders, you might have a ton of paginated search.
I think reducing your index size could be beneficial, but I'd make sure that the rental pages are the primary culprit first. I don't think the property URL change would help that much. It's a nice-to-have, but it wouldn't impact Panda or cause you major problems with Google the way it is. It's just slightly less user-friendly and slightly less keyword-targeted. I'd deal with the thin content first.