According to classical nucleation theory, nucleation from solution involves the formation of small atomic clusters. Most formulations of classical nucleation use continuum "droplet" approximations to describe the properties of these clusters. However, the discrete atomic nature of very small clusters may cause deviations from these approximations. Here, we present a self-consistent framework for describing the nature of these deviations. We use our framework to investigate the formation of "polycube" atomic clusters on a cubic lattice, for which we have used combinatoric data to calculate the thermodynamic properties of clusters with 17 atoms or less. We show that the classical continuum droplet model emerges as a natural approach to describe the free energy of small clusters, but with a size-dependent surface tension. However, this formulation only arises if an appropriate "site-normalized" definition is adopted for the free energy of formation. These results are independently confirmed through the use of Monte Carlo calculations. Our results show that clusters formed from sparingly soluble materials (μM solubility range) tend to adopt compact configurations that minimize the solvent-solute interaction energy. As a consequence, there are distinct minima in the cluster-size-energy landscape that correspond to especially compact configurations. Conversely, highly soluble materials (1M) form clusters with expanded configurations that maximize configurational entropy. The effective surface tension of these clusters tends to smoothly and systematically decrease as the cluster size increases. However, materials with intermediate solubility (1 mM) are found to have a balanced behavior, with cluster energies that follow the classical "droplet" scaling laws remarkably well.