The formation of nanopollutants in the atmosphere, raindrops in a cloud, and cosmic dust share a common physics, closely related to the nucleation of phase transitions. Unfortunately the theory at hand does not reproduce laboratory measurements beyond the order-of magnitude level. The key unknown is the physics and behavior of nanoclusters that are far more complex than a single molecule, yet not big enough to be considered solids (or liquids). In this talk I will focus on cosmic dust to introduce the theories of dust nucleation and formation. I will emphasize the major discrepancies between the model predictions and observations, underlying the need for a better understanding of the underlying physics. I will then discuss the various new ingredients that can be added to the theory to improve its performance and its ability to predict the properties and formation of nanoparticles. I will conclude by exploring the importance and ramifications of the knowledge that can be generated, ranging from everyday problems like rain and fog formation to the outstanding challenges of cosmology and climate change.