About 1M rows of data. Should I restrict myself to few columns as well?
Did you try it?

In general, I believe the curse of dimensionality is way overrated. As a rule of thumb, the curse of dimensionality refers to having more columns than rows. I doubt that you have 1M columns...

A robust algorithm, such as Logistic Regression, can often deal with sparse data. I sometimes get the feeling that this algorithm doesn't get the credit it deserves. Especially in production (due to high bias and low variance), I prefer it whenever possible. Nothing worse than an algorithm that fails in production...