The paradox you describe is even worse than the effect of gravity alone: Electrostatics works the same, attracting most matter at everyday distances very strongly by comparison. That is obvious for opposite charges, but even neutral matter attracts as electric interaction induces dipoles. Even where you have equal charges, which do repel each other, you do not end up with a stable floating arrangement (the Earnshaw theorem).
The answer is quantum mechanics: Electrons are fermions, which cannot occupy the same place in phase-space (the Pauli exclusion principle). Hence there are electronic states in atoms which, if occupied, will not be available to other electrons, not even partially (except in special mathematically orthogonal arrangements, the other states). Anything else coming close enough for wavefunctions to overlap experiences a repulsive force, which for any significant overlap is rather large. The result, at least if one were to visualize electrons as point-like rather than occupying their entire orbital, is that matter is essentially empty space.
If you are thinking more on astronomical or cosmological scales, your focus on gravity is correct. In that case, you balance inertia from the big bang with gravity (and possibly other forces, e.g. dark energy). For astronomical bodies, gravitational collapse occurs and is only slowed by conservation of angular momentum, which means that a part of the potential energy must first be turned into heat, which creates gas pressure that balances gravity. Then fusion occurs and that heating balances further collapse. Eventually, the same quantum mechanical effect, the Pauli exclusion principle, stabilizes a neutron star (where the electrons and protons have reacted to neutrons), and if that is not enough, you get a black hole. Which is the other answer to your question: Sometimes nothing does succeed in stopping gravitational collapse. I was temped to throw in the word "ultimately," but note that at least small black holes are not forever, because they shrink as they turn their mass into Hawking radiation.
EDIT: The accepted and vastly more popular answeraccepted and vastly more popular answer essentially points out that we do not know what ultimately happens in detail at the core of a black hole because we do not have a model (or theory) for that. That is certainly true: Even if you acknowledge attempts at building better theories (String theories tend to automatically be theories of quantum gravity), they certainly are not at a state where we could confidently predict what unknown fundamental particles with what masses yet await discovery. And as densities rise, just like electrons and protons react to neutrons to allow further compression, eventually one gets to ever more massive/energetic particles eventually beyond what we could currently have experimental knowledge of. But does it matter just how exotic the particles and energy inside of a black hole looks like in detail? As long as you stay on the outside, you will not get to see much useful evidence of its innermost interior anyways (in theory, there is information in Hawking radiation; in practice, that is useless thermodynamic entropy). Hence the question can largely be answered without a theory of quantum gravity, as this answer attempts to do.
