How to implement feature selection for categorical variables (especially with many categories)? I've been trying to get some ideas of how I could treat categorical variables when doing feature selection. Mainly I've been running Random Forest feature importance on Python for which preprocessing could play a big part.

For some variables which come with a large number of unique values such as State, Zip Codes, Cities...one hot encoding may not make sense since it explodes your vector length. Another issue is also how representative that category would be. Eg: If you have oly one observation from MI, does it really make sense to encode a feature for this state? What is considered the most appropriate way to treat variables like this?
Some algorithms will perform feature selection inherently - e.g. elastic net regression, random forest - so you will not necessarily need to do this prior to running the algorithm.

You've identified one issue with one-hot encoding - it may create exceptionally wide data sets. Another issue is that a feature selection technique based on one-hot encoded variables will identify important feature levels and not important features. I would argue you might want to keep your features "together" and not evaluate individual levels.

Have you considered some basic statistical tests? Sometimes simple methods are just as useful as complex approaches. Useful tests include ANOVA (continuous response, categorical predictors) and Chi-squared / Cramer's V tests of independence (categorical response, categorical predictors).