Alternatives for categorical prediction Upfront question:

What are some alternative methods for predicting categorical data?

Details:
I routinely process data that is 100% categorical. Almost always, this data is nominal (while, occasionally ordinal data such as 'quarters' may be included). When the time comes to run predictive modeling, I feel boxed-in to utilize only one method: multinomial regression models.
I have yet to have success employing randomForest or decision trees due to the amount of levels for the data (e.g., some variables have upwards of 111 levels in a set of 12000 observations).
I understand that, given the restricted data type, my options will be limited. However, I am wondering if anyone else has created predictive models with (only) nominal data and what method was chosen.


Note: I utilize R [3.6.1] for processing and modeling.
There are many supervised machine learning algorithms for classfication.
Here is a list to get you started:

Tree-based

Decision trees
Random Forest
Boosted Trees


Naive Bayes (NB)
K-nearest neighbors algorithm (k-NN)
Support vector machines (SVM)
Neural Networks / Deep Learning (DL)