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.