It feels like it should be possible to select who you maintain channels with to ensure a highly connected network. It doesn’t have to be random. I was thinking about articles I’ve read about Scale-Free Networks and how they appear in various systems like the human brain connectome.
I assume this is what your second topology diagram represents (with hubs). If you select the connections based on a routing algorithm like Kademlia as Angel Leon mentioned, you should be able to follow the channels in the direction of your target to derive a route.
I think your diagrams are misleading because they show graphs where each node is connected only to its local neighbours — in practice the edges would cross each other and parts of the graph shown as distant on your diagram would be connected by a few longer hops.
If everyone maintains a few local channels (to wallets near their address) and some distant channels (to wallets in other parts of the address space) then you should be able to route to any other node by following the channels themselves. There would be multiple routes to choose from, which means you should be able to send funds from any channel that is connected to a node closer to the destination wallet than you are, which means on average you should be able to make payments of at least 50% of your funded balance.
When talking about distance here I am talking about the XOR routing metric used in Kademlia.