What's the best way to approach a regression problem with a lot of features (over 300), many of which are categorical?

I have $$20,000$$ training examples of various candidate attributes (highest level of education, country, year of formal training completion, etc).

My output (prediction) will be for job_performance, which is measured between $$700$$ and $$4,200$$ (in my training data). Initially, I was thinking about putting together a fully connected neural network, but I attempted a similar problem in a Kaggle competition, but that didn't produce great results. What method(s) would you use to start?

Try doing a Principal component analysis to get the reduced feature set and then apply regression techniques in loop to see which one predicts better. SVM may take sometime to execute so better exclude it. Random Forest should be a good fit in this case.

I believe, RandmForest and Logistic regression from sklearn provide feature selection method, wherein it ranks the features by their importance in regression result. In R, similar is obtained from p-value of each feature.

Shamoon! If you want to do it in a right way. You need to think as well about an amount of time your model will work with 20Kx300 feature values.