Yes, the labeling changes everything. And makes it really hard to analyze.

Creating a random tree is very different from just assigning random parents. That being said, I'm also surprised that the expected height or diameter isn't logarithmic

I'm actually surprised its expectation is in $$$O(\sqrt{n})$$$! It's easy to show that the distribution of $$$\frac{d(1, 2)}{\sqrt{n}}$$$ converges to a distribution with pdf $$$x \mapsto x \cdot e^{-\frac{x^2}{2}}$$$. To do so, notice that there are $$$\binom{n-2}{k-1} \cdot (k-1)!$$$ possible paths of length $$$k$$$ between $$$1$$$ and $$$2$$$, and each of these paths appears in exactly $$$n^{n-k-2} \cdot (k+1)$$$ labeled trees. This latter formula can be proven in several ways, including by a slightly modified version of Prüfer sequences*. After a little re-arranging, the following proportionality drops out, from which the claimed limit is easy to recover:

*While there are at least $$$k+2$$$ vertices, remove the highest-index vertex which is a leaf and not on the path between $$$1$$$ and $$$2$$$, noting its parent. Then, when there are $$$k+2$$$ vertices, note the parent of the one vertex not on the path between $$$1$$$ and $$$2$$$. This produces a sequence of $$$n-k-1$$$ vertex numbers from $$$1$$$ to $$$n$$$, the last of which is on the path between $$$1$$$ and $$$2$$$. There are thus $$$n^{n-k-2}\cdot (k+1)$$$ such sequences, and every one corresponds to a unique labeled tree containing the path. Generally, the number of ways to merge $$$w$$$ components with sizes $$$s_i$$$ and total size $$$n$$$ is $$$n^{w-2} \prod s_i$$$.