Relays could advertise their current minimum PoW. Clients then pick the relays with cheapest PoW. This has the effect of distributing demand evenly across the network. Should I write a NIP? Basically this idea:

Hashcash Auctions for Decentralized Resource Allocation

Chris McCormick - News

Hey, any thoughts in using RandomX (CPU-only POW algo) for these kind of things? So that in long term more clients can provide their own POW and not have ASICs messing things up.

GitHub

RandomX/doc/design.md at master · tevador/RandomX

Proof of work algorithm based on random code execution - tevador/RandomX