Which model for feature importances? When wanting to find which features are the most important in a dataset, most people use a linear model - in most cases an L1 regularized one (i.e. Lasso).
However, tree based algorithms have their own criteria for determining the most important features (i.e. Gini and Information gain) and as far as I have seen they aren't used as much. Furthermore, they have the advantage of being interpretable (we know why a feature is more important than another).
Since tree-based algorithms (especially boosted ones) outperform linear models almost always, would it be safe to say that they are more reliable in appointing feature importances? Or does the low complexity of linear models lead to more robust features?
 A: Random Forest and other tree models are widely used for feature selection. For example, all the sklearn "tree" models return a feature importance vector after fitting, as do models fit by R's randomForest package. Features don't get implemented in every version of a popular algorithm if they're not being commonly used.
These "importances" are only strictly meaningful with respect to the original model that was fit, but since the tree model is able to utilize any kind of mutual information in any input variable, including non-linear and interactions with other variables, the fact that a random forest was never able to find any use at all for a particular variable regardless of which random subset of features were used to fit a tree provides fairly strong evidence that the independent variable in question is unrelated to the dependent variable. Therefore IVs with zero or almost zero importance are good candidates for exclusion during feature selection phase. On the other hand, just because a feature was given some importance by a RF model, that doesn't mean it can be successfully used by a linear model... I guess I would say the feature importance reported by RF have good specificity but medium-low sensitivity. 
l1 regularization (Lasso/ElasticNet) is mainly useful when you've already decided that you're going to build a white-box statistical model using an LM or GLM or some kind and have some idea of what the model specification should look like - which main effects you want, interaction terms, etc., and just want to make sure you aren't including anything which isn't statistically significant. Then l1 regularization is very close to a free lunch. Its fast and consistent - because the cost function is convex (but not strictly convex, unfortunately), a single invocation of the optimization algorithm will reach a global minima. The method can be justified from the point of view of Bayesian statistics as the choice of a particular prior.. It avoids the multiple hypothesis testing problems of stepwise feature selection.
Note this key difference: RF feature importance will tell you if there's any information to be squeezed out of a particular variable, perhaps in conjunction with several other variables, or perhaps as a non-linear effect. l1 regularization will drive a model parameter to zero if is already close to zero given the linear model that you have specified. 
This last point relates back to the final part of your question, "does the low complexity of linear models lead to more robust features?" And the answer there is "it depends." Yes, low complexity models, such as a model with only main effect terms, might be more robust... but it could also be under-specified. We have to check for heteroskedasticity, normality of the residuals, etc. In general, a model can have three failure modes:


*

*The regression model is "underspecified."

*The regression model contains one or more "extraneous variables."

*The regression model is "overspecified."


Of these, the only one which l1-regularization actually addresses is the second one, extraneous variables. It's up to you to address the first by ensuring that all possible meaningful interaction terms and polynomial terms are included, and to address the third by checking for multiple colinearity (or perhaps also including l2-regularization a la ElasticNet.)
