I believe the best way is to make the purchase of relays very seamless within Nostr clients, either as an included feature for Premium access, or one-click rent your own. I will attempt to make that into my new Nostr client (Nostria).
Perhaps the issue before has been that you purchase access to a larger shared relay, instead people should purchase their own relays. As long as Nostr clients implement the outbox-model nicely, it shouldn't be an issue discovering users and their content.
I wrote about "Discovery Relays" here, that should solve it and then everyone can have their own smaller set of relays, not needing large popular relays: