This is a problem I keep having both in the everyday life and sometimes during travelling: I'm going sightseeing and I plan to attend some kind of event where having a backpack would not be welcome, as in this question, but let's broaden it to all cities.
Let's say that my hotel reservation is done, where else should I be looking for a spot where I wouldn't spend fortune just for storing my bag? So far I learned that - at least in Poland - train stations often have baggage lockers that can be rented at a reasonable price.