The same problem can also be solved with signed messages, like the HTTP Signatures used by Mastodon and most of the other microblogging fedi servers. Signatures allow a message to flow peer-to-peer instead of requiring a direct connection. You would only need a connection when actively interacting with a post on another instance, and its very unlikely that all 10K instances would be interacting with each other. Most likely, the network will consist of smallish groups of loosely-related instances plus a few giant servers that can handle the load of being popular.
I feel like this design would work pretty well even for a modern phone. Just flatten the bottom-right menu section and extend the screen over it, and you’d get a regular full-size smartphone with a slide-out keyboard and some handy physical buttons!