Robust constraints and novel gamma-ray signatures of dark matter that interacts strongly with nucleons