I've often done similar things to the situation you describe in your question, but I've rarely ended up with the same problem you have. I think with a few small tweaks you might be able to get round it too...
Firstly, if you're going to spend the day doing anything in a city before a flight, you'll probably want to shower and change. Doesn't seem to matter to me what the temperature was predicted or actually, a day of doing stuff is enough. A shower freshens you up, helps de-stress etc. I'd say always plan to take one.
How though? Well, if you've been staying in a hostel, just ask at checkout. There's always some showers not in rooms, and I've never had issues with leaving my bags there, coming back later, showering and changing then leaving. You may even get a key for the communal areas too in the day. At hotels, I always speak to them around breakfast time. I explain that I'm going to want to do something in the day, then freshen up before finally departing, and ask if I can perhaps get access to the gym / sports facilities / etc to do that. Some times they'll give me a key when I checkout and leave my bags. Other times, they'll check the systems and give me a late checkout - asking at breakfast time seems to make this a lot more likely than asking at checkout time. Sometimes I can get a late checkout that's late enough for what I really wanted, often it's close enough (eg leaving on the airport bus at 6.30pm, late checkout until 5pm then wifi code + sit in lobby for a bit until the bus).
If that wasn't possible, eg the airport is in a different city to the hotel the night before, then try to shower at the departure airport. This might mean you'll need to pay for lounge access (assuming you weren't organised and didn't pick a flight where you'd get lounge access anyway), or might mean paying for dedicated showers, or might even mean an hour at an airport hotel. Can normally be done. That'll leave you fresh and de-stressed before boarding, which'll help a lot.
On arrival, if you have arrivals lounge access, great, job done! Otherwise check for a paid arrivals lounge, or an airport hotel - some airport hotels do a cheap rate for access to their sports facilities and a breakfast. If not, go straight to your hotel when you get into town. At the very least, you can then leave your bags before you go sightseeing. If it's a hostel, you'd be able to shower there, just ask and explain. At a hotel, say something like "Hi, I know I'm really early and checkin isn't for hours, but any chance I could grab a quick shower and then leave my bags for the day?". If they're not busy, they'll often sort you out with an early checkin then and there, especially if you ask in the local language. If not, you can normally get a pass to the gym, or worst case they might let you borrow a room that someone has just checked out of that hasn't been cleaned yet - it's better than nothing!
Another thing is to have a partial change or two of clothing with you. Even if nothing else is on offer, having a "sparrow bath" in the toilets at the airport then putting on clean socks and a clean tshirt can make a big difference to how you feel and smell. Probably best to take one of those microfibre towels with you if you do that though, as drying yourself off with some kinds of hand driers / paper towels can be "interesting"...