Surfaces and interfaces offer new possibilities for tailoring the many-body interactions that dominate the electrical and thermal properties of transition metal oxides. Here, we use the prototypical two-dimensional electron liquid (2DEL) at the SrTiO$_3$(001) surface to reveal a remarkably complex evolution of electron-phonon coupling with the tunable carrier density of this system. At low density, where superconductivity is found in the analogous 2DEL at the LaAlO$_3$/SrTiO$_3$ interface, our angle-resolved photoemission data show replica bands separated by 100,meV from the main bands. This is a hallmark of a coherent polaronic liquid and implies strong long-range coupling to a single longitudinal optical phonon mode. In the overdoped regime the preferential coupling to this mode decreases and the 2DEL undergoes a crossover to a more conventional metallic state with weaker short-range electron-phonon interaction. These results place constraints on the theoretical description of superconductivity and allow for a unified understanding of the transport properties in SrTiO$_3$-based 2DELs.