A day or two ago, I posted my nomination for the greatest mystery in all of physics: why is it that the "gravitational charge" (i.e. how strongly you couple to the gravitational field) is identically equal to your inertial mass (i.e. how strongly you resist being pushed around by any kind of force)?
Einstein's General Relativity is our modern theory of gravity, and it answers this question in an extremely satisfying and elegant manner. Specifically, gravity is not a force at all; it's the geometry of spacetime. All objects move through spacetime in as straight a line as they can; if they deviate from a straight line, it's simply because of the curvature of spacetime. Objects of different mass are moving through the same spacetime geometry, so they all will move in the same manner.
This, to me, is an amazingly simple and elegant solution to what seems to be a great conundrum. Yes, it's often convenient to talk about gravity as a force, but when we recognize it not as a force but just as the background of what's out there, the conundrum completely goes away. Quantum Mechanics is in many ways a more successful theory than GR, in that it has been much more widely tested, and its tests are more precise. But I find at least the "gravity is the curvature of spacetime" part of GR to be far more elegant and beautiful than quantum mechanics.
The first glimmerings of gravity as geometry come from Galileo. Apocryphally, he dropped objects of a different mass off of the tower in Pisa, and observed them falling at the same rate. In reality, he did his experiments by rolling things down inclined planes, but the conclusion was the same.
Many of us intuitively expect heavier objects to fall faster. After all, they are heavier, so gravity is pulling on them more. Wouldn't they then fall faster? But, because they are heavier, it takes greater force to make them fall, and the two effects exactly balance out.
Our intuition serves us, however. Drop a hammer and a piece of paper-- and the hammer will hit the ground first. The problem here is that the two aren't operating just under the influence of gravity, but also under the influence of air resistance, and the air resistance has a much bigger effect (relatively speaking) on the piece of paper than it does on the hammer. But if we were to do this experiment on the moon— as, indeed, astronauts did— we would see the two objects fall at the same rate. On the moon, there is no atmosphere to speak of, so the two objects are indeed both under the influence only of gravity.
Construct the following situation: you have a big charged ball (you could think of it as a proton, but let's go bigger to avoid quantum effects). This big ball (of mass M) has a positive charge. Now start with two negatively charged balls, both with exactly the same negative charge. However, one negatively charged ball (m1) is heavier than the other (m2). Set the two moving so that they'll orbit the positively charged ball. The electrostatic attraction between them will hold them in orbit around the positively charged ball. However, that orbit will not be the same. If the heavier ball (m1) is in a circular orbit, and the lighter ball starts with exactly the same velocity, it will go into a larger elliptical orbit.
Gravity is different. Two objects the same distance from the Earth, starting with the same velocity, will orbit at exactly the same rate, regardless of their masses. Rather than treating gravity as a force, we say that in fact spacetime is curved around the Earth. The orbiting object wants to fly off in a straight line, but can't becuase of this curvature of spacetime. As a result, it just falls around the Earth. But the slope of the curvature of spacetime is the same for all objects, because it's the same spacetime— so two different objects starting with the same velocity have exactly the same orbits.
There is often an analogy used to a bowling ball sitting on a trampoline, but I'm not completely happy with that analogy-- because there is a "down" direction in that analogy that doesn't really have an analog in curved spacetime.
Gravity as the curvature of spacetime— it's such a simple, elegant, beautiful concept that it almost pains me to think that efforts to unify gravity with quantum mechanics may result in our learning that General Relativity is just the effective limit of a deeper theory (much as Newton's gravity is an effective limit of GR).