On the basis of first-principles G0W0 calculations we systematically study how the electronic levels of a benzene molecule are renormalized by substrate polarization when physisorbed on different metallic and semiconducting surfaces. The polarization-induced reduction in the energy gap between occupied and unoccupied molecular levels is found to scale with the substrate density of states at the Fermi level (for metals) and substrate band gap (for semiconductors). These conclusions are further supported by self-consistent GW calculations on simple lattice models. By expressing the electron self-energy in terms of the substrate’s joint density of states we relate the level shift to the surface electronic structure, thus providing a microscopic explanation of the trends in the GW and G0W0 calculations. While image charge effects are not captured by semilocal and hybrid exchange-correlation functionals, we find that error cancellations lead to remarkably good agreement between the G0W0 and Kohn-Sham energies for the occupied orbitals of the adsorbed molecule.