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