Circumstantial evidence suggests that most known extra-solar planetary systems are survivors of violent dynamical instabilities. Here we explore how giant planet instabilities affect the formation and survival of terrestrial planets. We simulate planetary system evolution around Sun-like stars from initial conditions that comprise: an inner disk of planetesimals and planetary embryos, three giant planets at Jupiter-Saturn distances, and a massive outer planetesimal disk. We then calculate dust production rates and debris disk SEDs assuming that each planetesimal particle represents an ensemble of smaller bodies in collisional equilibrium. We predict a strong correlation between the presence of terrestrial planets and debris disks, mediated by the giant planets. Strong giant planet instabilities destroy all rocky material - including fully-formed terrestrial planets if the instabilities occur late - along with the icy planetesimals. Stable or weakly unstable systems allow terrestrial planets to accrete and significant dust to be produced in their outer regions. Stars older than ~100 Myr with bright cold dust emission (at ~70 microns) signpost the dynamically calm environments conducive to efficient terrestrial accretion. We predict that while the typical eccentricities of terrestrial planets are small, there should exist a novel class of terrestrial planet system whose single planet undergoes large amplitude oscillations in eccentricity and inclination. By scaling to the observed semimajor axis distribution of giant exoplanets, we estimate that terrestrial exoplanets in the same systems should be a few times more abundant at 0.5 AU than giant or terrestrial exoplanets at 1 AU. Finally, we discuss the Solar System, which appears to be unusual in combining a rich terrestrial planet system with a low dust content.