Warning, brain dump incoming.
Surely the only approach that could work is to select a performant relay at the point that data needs to be transferred (especially since most devices are connected to a relay they won’t use, and most of the others won’t be transferring data most of the time).
The obvious approach which comes to mind is, when data needs to be transferred, the devices open up connections to a handful of promising-looking relays, and blocks are pulled through all of them simultaneously. The ones which have less bandwidth naturally end up transferring less of the data. The least performant relays can be dropped to reduce the load on them.
Of course, that’s probably also the most technically challenging solution, and therefore the least likely to be completed…
Another idea is to let devices “rate” the relay they’re using: when transferring data through a relay, they tell a central point (the relaypoolsrv) what speed they’re getting. Other devices can consult this at the point that they start transferring data, allowing them to first hop to a higher-rated relay.
Of course this is open to abuse. Another option is to let the relay tell the relaypoolsrv what speeds its devices are getting in practice, but that’s open to a different kind of abuse. Maybe a combination of both…
EDIT: Although, thinking further, if devices monitor the performance they’re getting out of a relay, and move away from it if it’s significantly worse than advertised, then that limits the damage that someone can do by advertising themselves as a relay with unlimited capacity.
I remember a discussion somewhere else about allowing devices to announce alternate addresses for themselves (and others) over a normal connection between two devices (in addition to the discovery servers). That seems related to allowing devices to quickly announce a change in relay to each other.