How to implement feature selection for categorical variables (especially with many categories)?
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).