We analyze the structure of model NiN and CuN clusters (N = 55, 147) supported on a variety of atomically smooth van der Waals surfaces. The global minima are mapped in the space of two parameters: (i) the laterally averaged surface stickiness, γ, which controls the macroscopic wetting angle, and (ii) the surface microstructure, which produces more subtle but important templating via epitaxial stresses. We find that adjusting the substrate lattice (even at constant γ) can favor different crystal plane orientations in the cluster, stabilize hexagonal close-packed order, or induce various defects, such as stacking faults, twin boundaries, and five-fold disclinations. Thermodynamic analysis reveals substrate-dependent solid-solid transitions in cluster morphology, with tunable transition temperature and sometimes exhibiting re-entrant behavior. These results shed new light on the extent to which a supporting surface can be used to influence the equilibrium behavior of nanoparticles.