when speed is not a major concern, what is the best ML algorithm for high dimensional data? we are trying to build a predicting model using machine learning algorithms.

I have a use case where the input data have a very high dimension. Each sample point has 20000 features.

we have a decent training sample set with around 1 million training samples, if necessary, we can acquire more, say, 2 or 3 million.

We are not very speed sensitive, it's not like a recommendation system that needs to respond within a second. The application allows us to spend up to a couple of minutes for one prediction. Nevertheless, we hope the algorithm can be run in parallel mode in the future.

given above description, what kind of algorithm would you suggest? 

Our biggest concern is over fitting, with so many features, it seems that we are doomed to over-fit. 

We were trying to do something alone the line of nearest neighbor, but with these many features, calculating distance sounds like a mission impossible. Maybe we should do PCA to do dimension reduction first?

Any comment is welcomed!
There is no one-size-fits-all

Also, data dimensionality is not the same everywhere. Text data, which is inherently sparse, has a very different intrinsic dimensionality than e.g. random Gaussians.

For text data, linear SVMs are known to work very well.

RBF kernels do not work well with high-dimensional data, because they are distance-based at the core, and choosing the sigma parameter becomes next to impossible.

If you can "fold" dimensions, you also get very different behavior. Im image recognition, you usually have thousands of pixels. However, you never look at all of them at once. Instead, you use convolutional kernels that move over the data space, and they may have only say 32x32 pixels. That is still 1024 dimensions, but not millions anymore.