The cold dark matter paradigm describes the large-scale structure of the Universe remarkably well. However, there exists some tension with the observed abundances and internal density structures of both field dwarf galaxies and galactic satellites. Here, we demonstrate that a simple class of dark matter models may offer a viable solution to all of these problems simultaneously. Their key phenomenological properties are velocity-dependent self-interactions mediated by a light vector messenger and thermal production with much later kinetic decoupling than in the standard case.