Yep, why not both? Clients must bid for both connection slots and space in the fixed-size database. The underlying values could be computed dynamically as well, e.g. fixed database size could be based on disk size - if the relay owner adds more disk suddenly there are more slots and therefore they become cheaper.

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: https://mccormick.cx/news/entries/hashcash-auctions-for-decentralized-resource-allocation

This is a great idea. Hashcash auctions for real world resources.

This is pretty great. Nice work Nostr devs!

Lol