Gamma-ray observations have long been used to constrain the properties of dark matter (DM), with a strong focus on weakly interacting massive particles annihilating through velocity-independent processes.However, in the absence of clear-cut observational evidence for the simplest candidates, the interest of the community in more complex DM scenarios involving a velocity-dependent cross-section has been growing steadily over the past few years.We present the first systematic study of velocity-dependent DM annihilation (in particular $p$-wave annihilation and Sommerfeld enhancement) in a variety of astrophysical objects, not only including the well-studied Milky Way dwarf satellite galaxies, but nearby dwarf irregular galaxies and local galaxy clusters as well. Particular attention is given to the interplay between velocity dependence and DM halo substructure. Uncertainties related to halo mass, phase-space and substructure modelling are also discussed in this velocity-dependent context. We show that, for $s$-wave annihilation, extremely large subhalo boost factors are to be expected, up to $10^{11}$ in clusters and up to $10^6-10^7$ in dwarf galaxies where subhalos are usually assumed not to play an important role. Boost factors for $p$-wave annihilation are smaller but can still reach $10^3$ in clusters. The angular extension of the DM signal is also significantly impacted, with e.g. the cluster typical emission radius increasing by a factor of order 10 in the $s$-wave case. We also compute the signal contrast of the objects in our sample with respect to annihilation happening in the Milky Way halo. Overall, we find that the hierarchy between the brightest considered targets depends on the specific details of the assumed particle-physics model.