Atoms and molecules adsorbed on metals affect each other indirectly even over considerable distances. Via systematic density-functional calculations, we establish the nature and strength of such interactions, and explain for what adsorbate systems they critically affect important materials properties. This is verified in kinetic Monte Carlo simulations of epitaxial growth, which help rationalize a number of recent experimental reports on anomalously low diffusion prefactors.