Semiconductor quantum dots have long been considered artificial atoms, but despite the overarching analogies in the strong energy-level quantization and the single-photon emission capability, their emission spectrum is far broader than typical atomic emission lines. Here, by using ab-initio molecular dynamics for simulating exciton-surface-phonon interactions in structurally dynamic CsPbBr quantum dots, followed by single quantum dot optical spectroscopy, we demonstrate that emission line-broadening in these quantum dots is primarily governed by the coupling of excitons to low-energy surface phonons. Mild adjustments of the surface chemical composition allow for attaining much smaller emission linewidths of 35-65 meV (vs. initial values of 70-120 meV), which are on par with the best values known for structurally rigid, colloidal II-VI quantum dots (20-60 meV). Ultra-narrow emission at room-temperature is desired for conventional light-emitting devices and paramount for emerging quantum light sources.