Since the predictors are all genes I presume that means they are all binary variables (either true or false depending on whether a person has that gene).

First of all you can do some Principle Component Analysis (PCA) on your data to remove some features which add little to the overall variance in the data. This technique captures the most variation for a given number of features so it will maximize the information you have in a set number of features.

This will transform your features from binary to continuous (the validity of this is discussed in the top answer to this question).

The golden rule is to start simple and work towards a more complicated model. You only want a classifier not an inference of what is causing a true/false classification so this opens up your model possibilities greatly. Logistic regression is a basic model which you can start with (and also allows for inference). Perhaps after that you can ask a follow up question with more details of your progress.

Since the predictors are all genes I presume that means they are all binary variables (either true or false depending on whether a person has that gene).

First of all you can do some Principle Component Analysis (PCA) on your data to remove some features which add little to the overall variance in the data. This technique captures the most variation for a given number of features so it will maximize the information you have in a set number of features.

This will transform your features from binary to continuous (the validity of this is discussed in the top answer to this question).

The golden rule is to start simple and work towards a more complicated model. You only want a classifier not an inference of what is causing a true/false classification so this opens up your model possibilities greatly. Logistic regression is a basic model which you can start with (and also allows for inference). Perhaps after that you can ask a follow up question with more details of your progress.