Maintaining the expander graph property and protecting the network against accidental partitioning and the randomness property which makes adaptive attacks not have big sibyl advantages are far more important that propagation speed.
Thanks for the clarification! I should have taken a moment to refresh myself with addrman, the comments and the code make it obvious that getaddr is returning a list of known nodes, without RPC access to call getpeerinfo - there's no easy way to learn the connected peers.
Agreed, it would very tricky without implying some trust between certain peers, e.g. some kind of hierarchy of nodes and "super" nodes. This would be incongruent with the core idea of a trustless p2p network.