Generally for structured data (i.e. each column represents a distinct type of information, such as 'revenue' or 'color') you'll want random forest or GBM.

For unstructured data, where you'll need lots of complex feature engineering, you'll generally want to let the model learning those features - so use deep learning. E.g. images, natural language, audio...

I've won competitions with random forests and teach deep learning - both definitely have their place, but they are generally for quite different types of data. (This may change in the future, however, with deep learning showing that it has the potential to work well for structured data too.)

(Don't worry about the No Free Lunch theorem - it has little to do with predictive modeling in the real world. Recent research shows that a random forest will give amongst the best results for the vast majority of real world datasets.)