You might want to read Chapter 18, "High-Dimensional Problems: When $p \gg N$", of Elements Of Statistical Learning.

Regarding your specific points (not in order):

The widely-accepted procedure of the false discovery rate addresses your point 3. While there are variations, the basic idea is to calculate the p-value for each feature, then sort them in increasing order. Following that, you conceptually plot a graph whose x axis is $1, ..., N$, and plot the $N$ p-values. You also run a line starting at the origin with slope $\alpha$, and select all features whose p-values are below the line, until the first one that is over the line. It can be shown that under certain conditions, $\alpha$ determines the false-positive rate, irrespective of $N$.

For 2., you can run cross-validation (if you have enough computing power, using the entire 200 folds - note that this is trivially parallel). In each iteration, run some massive dimension reduction technique (e.g., supervised principal components), and check the performance on the holdout data.

1., in its most general form, seems to me unsolvable. With enough (random) features, two sets will differ. If you restrict things, though, to questions such as the values for feature $i$ in set 1 are higher (lower) than those in set $2$, you can again use FDR (false discovery rate). Once again, find the p-value for any such hypothesis, and select those beneath the line.

You might want to read Chapter 18, "High-Dimensional Problems: When $p \gg N$", of Elements Of Statistical Learning.

Regarding your specific points (not in order):

The widely-accepted procedure of the false discovery rate (see Section 18.7 in Elements Of Statistical Learning") addresses your point 3. While there are variations, the basic idea is to calculate the p-value for each feature, then sort them in increasing order. Following that, you conceptually plot a graph whose x axis is $1, ..., N$, and plot the $N$ p-values. You also run a line starting at the origin with slope $\alpha$, and select all features whose p-values are below the line, until the first one that is over the line. It can be shown that under certain conditions, $\alpha$ determines the false-positive rate, irrespective of $N$.

For 2., you can run cross-validation (if you have enough computing power, using the entire 200 folds - note that this is trivially parallel). In each iteration, run some massive dimension reduction technique (e.g., supervised principal components) (see Section 18.6 in Elements Of Statistical Learning") , and check the performance on the holdout data.

1., in its most general form, seems to me unsolvable. With enough (random) features, two sets will differ. If you restrict things, though, to questions such as the values for feature $i$ in set 1 are higher (lower) than those in set $2$, you can again use FDR (false discovery rate). Once again, find the p-value for any such hypothesis, and select those beneath the line.