Keep a wet towel around your neck. Wipe your face from time to time.
(Nethack fans will do it with #wipe)
Evaporation of water on your skin will cool your skin. Physical reason is latent heat.
Cooling base of neck has a medical reason (2009, Han et. al) resulting in cooler body. Blood vessels near skin transport a lot of blood towards the head and can be ...
You can make a mobile face cooling hat with a portable fan (I'd suggest something like this), some ducktape, and a hat (I'd suggest a hardhat). Just tape the fan to the hat in such a way that it's touching facing your face and BAM! Mobile face cooler.
Maybe you need a two-step approach. I don't have a brand to recommend. I have a technique you might find helpful.
Keep your cheap cleats; but, put them on over a pair of rubber overshoes which will stiffen the soles and protect your polished shoes from wear and tear of the cleats rubbing against your dress shoes.
Step 1. Shoe protection
Step 2. Put your ...
Take some old socks, the more coarsly knitted the better, and pull them over your shoes.
It really works, people in Croatia and neighbouring countries sometimes do this in winter.
Anyway, you asked for cheap, not fashionable.
I put the "webbed" side of Velcro on the bottom of mine. Just cut a long strip and attach it to each side of the shoe. I haven't had any problems sliding after that.
Also, I picked up a couple of packages of Non Slip Shoe Grip at my local Dollar Tree. They work great too.
The simplest way to prevent pebbles under your foot is to wear a form of sandal with enclosed heel, toe, and instep. It's called a "shoe" or, in a more extreme form, a "boot". Shoes, and especially boots, are much more resistant to pebble (and, to a lesser extent, sand) getting under the foot.
In general, when you are faced with difficult physical activity and you'd like to do it more efficiently, one of the tried and true methods of increasing efficiency is to repeat the activity over the course of several weeks or months until it is no longer difficult. This is often referred to as "exercise" (source):
physical activity that is done in ...