Single layer Pb on top of (111) surfaces of group IV semiconductors hosts charge density wave and superconductivity depending on the coverage and on the substrate. These systems are normally considered to be experimental realizations of single band Hubbard models and their properties are mostly investigated using lattice models with frozen structural degrees of freedom, although the reliability of this approximation is unclear. Here, we consider the case of Pb/Ge(111) at 1/3 coverage, for which surface X-ray diffraction and ARPES data are available. By performing first principles calculations, we demonstrate that the non-local exchange between Pb and the substrate drives the system into a $3times 3$ charge density wave. The electronic structure of this charge ordered phase is mainly determined by two effects: the magnitude of the Pb distortion and the large spin-orbit coupling. Finally, we show that the effect applies also to the $3times 3$ phase of Pb/Si(111) where the Pb-substrate exchange interaction increases the bandwidth by more than a factor 1.5 with respect to DFT+U, in better agreement with STS data. The delicate interplay between substrate, structural and electronic degrees of freedom invalidates the widespread interpretation available in literature considering these compounds as physical realizations of single band Hubbard models.