Large no of categorical variables with large no of categories
I used to work a lot with such data in the past.
When you have many categorical features with high cardinality, you must avoid one-hot encoding them because it consumes too much memory and above all trees built from them will be too deep and worse than trees built without one-hot encoding.
You need a Tree based model library implemented with native categorical feature support (i.e. not needing the categorical features to be one-hot encoded).
I suggest you to use one of those 4 implementations :
- CatBoost
- LightGBM
- H2O GBM
- H2O Random Forest
Scikit learn and XGBoost implementations still need one-hot encoded categorical variables so I don't recommend using one of these libraries if your dataset has high cardinality categorical variables (i.e. with more than about 10 levels/categories).
See this :  


  LightGBM offers good accuracy with integer-encoded categorical
  features. LightGBM applies Fisher (1958) to find the optimal split
  over categories as described here. This often performs better than
  one-hot encoding.