We investigate the structure of metastable states in self-generated Coulomb glasses. In dramatic contrast to disordered electron glasses, we find that these states lack marginal stability. Such absence of marginal stability is reflected by the suppression of the single-particle density of states into an exponentially soft gap of the form $g(\epsilon )\sim {{\rm{e}}}^{-V/\xi | \epsilon | }$. To analytically explain this behavior, we extend the stability criterion of Efros and Shklovskii to incorporate local charge correlations, in qualitative agreement with our numerical findings. Our work suggests the existence of a new class of self-generated glasses dominated by strong geometric frustration.