But, because this is fraction rises with both D and U, these research
papers rightly point out that you can't keep adding relays *and* users
and expect Tor to scale.

Broadcast a fraction of all available directories? Use md5 as a random number generator, hash the ECC/RSA keys using md5. A user connecting to the network will generate an 8-bit random value, and based on that, will download one of 1/256 directories.

Right now, any relay with more than ~100Mbit of capacity really
needs to run an additional tor relay instance on that link to make
use of it. If they have AES-NI, this might go up to 300Mbit.

Any plans to use ChaCha8 instead of AES? It would an order of magnitude faster. It is also unlikely for ChaCha8 to become sufficiently insecure to effect web-size non-video traffic.