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](http://en.wikipedia.org/wiki/Earnshaw%27s_theorem)).

The answer is quantum mechanics: Electrons are fermions, which cannot occupy the same place in phase-space (the [Pauli exclusion principle](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Hawking_radiation).