Algorithm for Binary classification
First thing that comes to my mind is to do different encodings. There are some ways to deal with high cardinality categorical data such as: Label Encoding or the famous target encoding. Before anything else I will recommend changing the encoding type.
But, since your question about which predictor use with small and space data. I will go still with logistic regression, decision tree or SVM. When data is small all algorithms tend to work quite similar.
Things like Random Forest might perform well since they do bootstrapping what tends to be a way to sample your data with replacement.