I just want to chime in and highlight that using clustering to segment your data before modelling might be a bad idea.
At a high level, clustering is a two/three dimensional visualisation of similarity.
If you have two/three dimensions to your dataset you're probably OK using clustering to segment your data as all the possible relationships are being visualised by the clustering.
However if you have more than three variables than this you won't be able to visualise all the possible relationships meaning that using the 2D/3D clustering might find patterns that are not there. See Steinbach, Ertöz, and Kumar for more information.
That being said you could use dimensionality reduction techniques to reduce the dimensionality of the dataset to two/three dimensions and then cluster your population- but this is situational.
By reducing the dimensionality of your dataset to get cluster-able results you might be throwing away information that would be useful when it comes to modelling.
Also: I'd recommend using a more formalised metric for deciding the adequacy of your clustering see here - maybe you're using too many/not enough clusters?
I've only answered your half of your question so now I'll attempt the second part: when in doubt, Random Forests are your best friend. Use them as your baseline prediction and you'll be getting great accuracy out of the box.