We set the strongest limits to-date on the velocity-independent dark matter (DM) - proton cross section $\sigma$ for DM masses $m = 10\,\mathrm{keV}$ to $100\,\mathrm{GeV}$, using large-scale structure traced by the Lyman-alpha forest: e.g., a 95% lower limit $\sigma < 6 \times 10^{-30}\,\mathrm{cm}^2$, for $m = 100\,\mathrm{keV}$. Our results complement direct detection, which has limited sensitivity to sub-GeV DM. We use an emulator of cosmological simulations, combined with data from the smallest cosmological scales used to-date, to model and search for the imprint of primordial DM-proton collisions. Cosmological bounds are improved by up to a factor of 25.