To eliminate segmentation, every peer should have a list of every other peer. Tor also has this requirement, so we should copy them: have several trusted directory servers periodically create a signed list of all peers and publish it via HTTP. All BitCoin clients have the option to act as a directory mirror, which will be indicated in the dirServers’ list. Generators need to ask to be added to the list (which could also include info like the maximum number of connections that peer will accept), but people just wishing to make transactions can just get the list from a dirMirror and connect to a few random peers.
If this is too centralized, we can do what I2P did and allow anyone to become a directory server. You need to be able to detect when a dirServer goes rogue in this case, though.