Hermes Boots have tinker-compatible alternatives in both the Snow and Desert biomes, as well as via Fishing. You say that isn't reliable or are equally rare, but I consider this quite an array of sources for getting such an item.
Indeed, boots have a few alternatives, but due to their overall rarity it doesn't really matter in the long term. Aside from exploring simply accessible parts of 2-3 biomes to increase the chest loot sample size (which you still need to get to without boots, and Desert is another can of
tomb crawlers)
I'd give an example: Slime Staff has a total of ~18 Pre-HM sources but still is widely considered an extremely rare item. A bit of exaggeration, but hopefully that'd be enough.
Then again: it's not me being salty about not having boots 15 minutes after I enter the world. It's about how this item ends up being a handicap/stale goal to complete in so many runs for no greater reason than randomness, to the point where several hours are spent looting only for them,
... and about how they are one of the least replaceable items.
Taking the Lucky Horseshoe as an example: You can negate fall damage without one with: nearly guaranteed to encounter Grappling Hooks, somewhat reliable Rocket Boots/upgrades, any Double Jump bottles, upcoming Fledgling Wings, certain mounts, could even go as far as placing/seeking for cobweb/water, and even partially negate it with Frog Leg. Fair share of possibilities for a secondary mechanic (because it can also be negated with careful landscape designing/traversing)
Now, the Boot accessories. What would be the analogues? Some mounts, movement speed stacking, and partially speeding up by Grappling Hooks. That's for a mechanic that you cannot really avoid: walking faster.
Not the sweetest way to let players play the game, to be honest. I can endure that (hell, there is a whole playthrough of not moving by legs in first place), but that's not particularly enjoyable design to stumble across regularly.