The recent detection of an anomalously strong 21-cm signal of neutral hydrogen from Cosmic Dawn by the EDGES Low-Band radio experiment can be explained if cold dark matter particles scattered off the baryons draining excess energy from the gas. In this Letter we explore the expanded range of the 21-cm signal that is opened up by this interaction, varying the astrophysical parameters as well as the properties of dark matter particles in the widest possible range. We identify models consistent with current data by comparing to both the detection in the Low-Band and the upper limits from the EDGES High-Band antenna. We find that consistent models predict a 21-cm fluctuation during Cosmic Dawn that is between 3 and 30 times larger than the largest previously expected without dark matter scattering. The expected power spectrum exhibits strong Baryon Acoustic Oscillations imprinted by the velocity-dependent cross-section. The latter signature is a smoking gun of the velocity-dependent scattering and could be used by interferometers to verify the dark matter explanation of the EDGES detection.