The algorithm you describe is at each stage isomorphic to an algorithm for picking a particular tree from the "Uniform Spanning Tree" (which is THE uniform distribution of all possible spanning trees) when applied to any finite fully connected graph.

One standard method is to iterate choosing new points at random (uniformly from the unconnected ones) and performing a "Loop Erased Random Walk" until "hitting" the existing tree.

The isomorphism of algorithms is because such a fractal growth process is uniform so we can modify it at each LERW by removing the irrelevant intermediate points.  This is just shrinking the graph by removing nodes on a line without changing "connected-ness".

The large-scale symmetry under permutations is due to the "uniform probability" property of all finite sub-trees.

Bit of a hand-wavy argument so far I know but UST is the way to go.  A fully connected graph is a simpler starting point than the 50% connected Rado graph but ..
**Corollary ..**
I imagine any graph with a bounded below probability of connected-ness must almost surely have "THE random tree" as a sub-graph as n grows.  Average density of connections of "THE random tree" is $\frac2{n-1}$ and expected neighbours of $k$'th point is $\sum_{i=k+1}^n\frac1i$, so by permuting a large sub-graph of Rado to order the most connected points earliest we can comfortably exceed this everywhere and select at least one tree with probability approaching $1$ as $n\rightarrow\infty$.