Get estimates about 'variable importance' across a large number of variables and their permutations My client would like to know which, of many different kinds of product dimensions, are most important for perceived quality.  Some of the dimensions are as follows: price, material, country of origin, whether or not your colleagues/friends have the product, and so on.  Most of these dimensions include many levels (price, for example, can be from $1 - $1000; material can include steel, plastic, and so on; country of origin includes 10 possible countries). 
We want to be able to answer general questions like: which of these factors are most important in predicting customer appraisals of quality?  My client has created a survey in which a random sample of, say, three of these variables are shown to a customer (e.g. a 100 dollar, plastic, widget from China; a 500 dollar metal drum from Cambodia, etc.), and the customer rates how high they perceive the quality to be. 
Coming from an econometric background, it's not clear how to answer this kind of question using my normal tools.  There seems to be an enormous number of combinations of variables, and the potential for countless interaction effects seems overwhelming to interpret. 
I've come across literature on conjoint analysis and taguchi methods, which seem relevant, but the articles I've found seem to broadly describe design principles, rather than the mechanics of the analytical strategy.  
Random forests with variable importance seems promising, but it's not clear how to recover regression-esque effect sizes from forests, nor is it clear how to get a sense of which interactions are most relevant. 
Perhaps some kind of Lasso regression?  Would I fully specify all the interactions, and run a Lasso procedure?  I'm worried it may select non-sensical interactions.  
Apologies if the question is poorly specified.  I'd like to be able to say, "If your product is coming from China, characteristics X, Y, Z are most important.  If you are selling a plastic tool, characteristics A, B, C, are most important."  
 A: Be cautious - most analysts do not use the bootstrap to get confidence intervals for variable importance measures, but when they do they are usually disappointed.  The data, unless massive, do not contain sufficient information to tell you reliably which elements of the data are predictive, and do not have sufficient information for telling you how important each potential predictor is.  I expand on this in Chapter 20 of BBR.  See also this for a discussion of measures of added information.
A: In my field (political science) conjoint experiments are very common. Typically the data come in the form of a forced-choice comparison — i.e., survey respondents are shown a series of comparisons between product profiles in which features of the products are randomized, and then respondents choose which product they prefer. 
In terms of analysis, a paper by Hainmueller, Hopkins, and Yamamoto shows that you can estimate a quantity called the average marginal component effect (AMCE) by a linear regression (using OLS) of the form
$$Y_{ij} = a + \beta_1 X_{1ij} + \beta_2 X_{2ij} + \cdots + \epsilon_{ij},$$
where $Y_{ij}$ is an indicator for whether respondent $i$ chose profile $j$ when they had the option, and the $X$'s are vectors of indicator variables for the features. The AMCE is the average change in probability of choosing a product that has that specific feature, relative to the baseline, marginalizing over the distribution of other features. In other words, it averages over all possible interactions effects. This is a very simple estimator to implement since it's just OLS. 
If you want to know how the importance of specific factors varies as a function of other factors, you could subset based on the other factor (e.g. whether the product was made in China) and re-estimate the regression above, or you could simply include interaction indicators. As you note, though, you can't estimate all possible interactions using OLS, since the number of combinations very quickly exceeds the number of respondents. Your idea to use LASSO makes sense to me. To see another estimator for this problem that has some nice properties, you could take a look at this paper by Egami and Imai.
A: There are a whole host of options to determine variable importance. As you mentioned random forest has a variable importance metric built in. R package DALEX also has a model agnostic approach similar to the random forest importance but is model agnostic.  When you say these don’t have effect sizes I would disagree and say they are quite interpretable.
I would also suggest information theoretic methods such as information gain, though this assumes conditional independence between variables.
Lastly you could look at the relief algorithm which to some extent considers dependence between predictors and works with all variable types
A: Have you tried to look at Pareto-smoothed importance sampling (PSIS) by Vehtari, Gelman and Gabry?
Here's a fast recap: "Pareto-smoothed importance sampling (PSIS), a new procedure for regularizing importance weights". Look at the examples in the paper. It should be a good starting point. If it seems sounding to you there's an R package called ```loo`` to work on these concepts.
