This is a very broad question, so I am going to give a very brief overview of typical exponentially-scaling problems. I am not an expert in most of these areas, so any suggestions or improvements will be welcome.
Solving the Schrödinger equation
In order to solve the Schrödinger equation numerically, you need to diagonalise a rank $3N$ tensor -- as you can see, a pretty impossible operation not only in terms of CPU power, but also in terms of memory. The main problem in fact is that the wavefunction has to be antisymmetric with respect to all electrons, which is the main reason for combinatorial explosion. An alternative way is to expand the wavefunction as a multivariable Taylor series of antisymmetric functions (determinants), and if you were to do it exactly (full configuration interaction), it also scales exponentially. So at this point you can either solve the equation by ignoring most of the correlation between different degrees of freedom (Hartree-Fock, Moller-Plesset perturbation theory, truncated configuration interaction), project the $3N$-dimensional problem onto a 3-dimensional one, where the exact solution is unknown, but able to be approximated (density functional theory), or solve the correlated problem exactly for an idealised approximate infinite sum (coupled cluster theory). Another way to solve the equation is to convert it to a sampling problem (diffusion quantum Monte Carlo), which is exact for bosons, but needs an approximation for fermions (fixed node approximation), so that it doesn't scale exponentially. There is a lot of literature on making a lot of the above methods linear-scaling using clever approximations or making the formally exact full configuration interaction method more efficient (full configuration interaction quantum Monte Carlo), but in general, the more computational time you throw in, the larger the class of problems your method can tackle and some of the above approximations are better (and slower) than others.
Exploring potential energy surfaces
This is related to the sampling problem which I will address later. Here you convert a $3N$-dimensional sampling problem into a 1, 2 or 3-dimensional one, where you only care about particular nonlinear degrees of freedom (reaction coordinates, collective variables). This gets rid of the exponential scaling, but also needs a certain knowledge of the best/relevant collective variables, which are typically unknown. So this approach is similar in spirit to density functional theory - you convert your problem into a simple one, for which you don't know the exact method and you have to make an educated guess. In terms of sampling nuclear quantum effects, the problem is particularly badly scaling and common methods to estimate typical correlation functions/constants of interest is to either approximate them as simpler classical problems (semi-classical transition state theory), or to convert them into a sampling problem (ring polymer molecular dynamics). The latter is very similar in spirit to diffusion Monte Carlo for electronic structure.
As with all optimisation algorithms, finding a global minimum is an exponentially scaling problem, so to my knowledge, most minimisation algorithms in computational chemistry provide local minima, which scale much better but are also more approximate. In classical computational chemistry you could afford to go one step further and explore much wider conformational space by heating your system up and slowly cooling it down to find some other better minima (simulated annealing). However, as you can see, the result you obtain from this will be highly dependent on chance and convergence will still be exponentially scaling -- there is no way around this.
This is one of the biggest unsolved problems in classical computational chemistry. As usual, local sampling is straightforward and typically scales as $3N\log 3N$ (Markov chain Monte Carlo, leapfrog/any other integrator), whereas enhanced sampling either resorts to using collective variables (metadynamics, umbrella sampling) or providing "locally global" sampling, by smoothening kinetic barriers (replica exchange, sequential Monte Carlo). Now, kinetic barriers slow down local sampling exponentially, but the above methods smoothen these linearly, resulting in cheaper locally enhanced sampling. However, there is no free lunch and global convergence will still be exponential, no matter what you do (e.g. protein folding problem).
Partition function calculation
The partition function is a $3N$-dimensional integral (I am going to focus on the classical case, as the quantum one is even more difficult). One way is to try to estimate the partition function (nested sampling, sequential monte carlo), where your convergence will typically scale exponentially but still much, much more efficient than regular quadrature (see exact diagonalisation of the Schrödinger equation, similar problem). This is very difficult, so we typically only try to calculate ratios of partition functions, which are much more nicely behaved. In these cases you can convert the integration problem into a sampling problem (free energy perturbation, thermodynamic integration, nonequilibrium free energy perturbation) and all above sampling issues still apply, so you never really escape the curse of dimensionality, but you get some sort of local convergence, which is still better than nothing :)
So in conclusion, there is no free lunch in computational chemistry and there are various classes of approximations suitable for different problems and in general, the better scaling your problem is, the more approximate and less applicable in general it is. In terms of "best value" nearly exact methods, my vote is on path integral methods (diffusion Monte Carlo, ring polymer molecular dynamics, sequential Monte Carlo), which convert the exponentially scaling problems into polynomially scaling ones (but still with convergence problems) -- although not perfect, at least you won't need all the atoms of the universe to run these and you won't need to know the answer to get the answer, which is sadly an overwhelming problem in many subfields of computational chemistry.