I got refused a rental in the middle of Manhattan once because I wouldn't show them a return flight ticket (I actually did have one, but it's none of their business).
I charged the company back via my credit card provider, and have never even considered doing business with that company again.
What company?
That one was Hertz. I use Avis pretty much exclusively now. They're mostly "ok" but certain pickup locations (SFO for example) are notoriously terrible at actually having a car ready like they are supposed to.
The most recent one for me was in Chicago at Routes Car Rental, and yes it was near the airport. It has also happened to people in my group in New York and New Jersey.