I'd say for standard SUV, you've got a pretty good shot at finding one on the lot with leather. Most Explorers & Terrains I've seen have leather. The only non-leather Venzas I've seen are in MDT where they're a franchise & always have low-end vehicles. I've not seen a 4Runner with leather. The others I can't comment on.

If you're ok to downgrade, there have been lots of Escapes on the lots lately and a good bit of those are leather. However, if you're renting 1-way, you're pretty much at their mercy to see what they want to get rid of.