Say I sample $n$ points uniformly at random in the unit square, and then I look for the shortest path through $\sqrt{n}$ of those points (rounding up, say). What happens to the length of this path as $n\rightarrow\infty$? Does it increase, decrease, or converge (or "none of the above")?



Shortest path through $\sqrt{n}$ points out of $n$
The following is a partial answer.


It is useful to rescale. So think of a Poisson process in the plane and consider the box of side $n$. There will be roughly $n^2$ points there. 
Let $A\_{[a,b]}$ be the random variable you described, but in the box $[a,b]^2$. You are really interested in $A\_{[0,n]}/n$. You have essentially that $A\_{[0,2n]}\leq A\_{[0,n]}+A\_{[n,2n]}$ (there is an error due to the segment connecting 
the path in the first box and the path in the second; probably that error is negligible but I did not check that). An application of the sub-additive ergodic theorem then gives that $A\_{[0,n]}/n$ converges to a deterministic number. Going from a Poisson number of particles to a fixed number of points is routine.


The above argument becomes rigorous if you ask your path to start at $(0,0)$ and end at $(1,1)$ and go through $\sqrt{n}$ points. 


A simple bound (independent of the above reasoning) is obtained by looking at the longest (in terms of number of points) increasing path. This is equivalent to the length of the longest increasing subsequence of a random permutation, and the number of points is $(2+o(1))\sqrt{n}$. The length of the increasing path going through all these points is roughly $\sqrt{2}$. You can of course 
take only $\sqrt{n}$ of these points, I do not think the length will change much. Interestingly, the constant $\sqrt{2}$ shows up again, as in John's answer. I suspect this might be the correct answer. Did you try to simulate?


