Which classification model to use on large, high-dimensional dataset?
I don't really have experience with such a massive dataset, but my first thought would be to explore the instances in order to see if so many are needed. I would start with an ablation experiment, trying various sizes of training data with a simple method (random forest seems a good idea) in order to observe the evolution of the performance w.r.t size of the training data. It's likely that the performance reaches a plateau at some point, and it would be useful to know this point.

It might also make sense to study if the data contains duplicates or near duplicates. You can't remove duplicates directly because the distribution matters, but it might be possible to replace them by assigning weights to instances. I'm not expert in this but there are methods for instance selection.