I actually recently wrote a paper on this subject which will appear at NIPS 2018: https://arxiv.org/abs/1806.08805
My collaborator and I proved that in the limit of an infinite number of dimensions the projection of a random walk onto any PCA component is a sinusoid. You are welcome to read the paper for the proof, but perhaps I can attempt a slightly more intuitive explanation.
The random walk process is a translation invariant process. No matter how many steps you take and how far away you get from the origin, the process that determines the next step is exactly the same. (This is in contrast to an Ornstein-Uhlenbeck process, for example, which is a random walk in a quadratic well. In this case the process that determines what your next step will be depends on your distance from the origin.)
Now, the eigenfunctions of any translation invariant operator are Fourier modes. Why is this? Well, in order to be translation invariant, the eigenfunctions need to be periodic, and in order to be an orthogonal basis, they need to be mutually orthogonal. The set of functions that satisfies these properties is the Fourier basis.
As for your second question about two independent random walks seeming to be correlated, this is just an illusion. Although the projection of the trajectory of both random walks onto their first PCA component will be a cosine, the direction of the first PCA component will be completely random. An an analogy, if you do two random walks, each of 10^6 steps, you can be quite sure that both will end up at a distance of about 1000 from the origin. But the two walks had nothing to do with each other, and furthermore the direction that the walk happened to go will be different each time.