I once booked a hotel in Los Angeles--it was not a hotel but a motel. When I was checking out, I wanted to leave a bag with them for retrieval later in the day, they refused.
After 9/11 (and even before), public lockers began disappearing.
Fortunately my bag was small, and I went to Universal Studios (for a tour), and they did have (small) lockers.