Falling with same acceleration and meaning of gravity My question is what does falling with same acceleration has to do with what Einstein concluded concerning the gravity in terms of the curvature?
 A: The statement that:

all bodies fall with the same acceleration in a gravitational field

is the weak equivalence principle, which has been experimentally tested and so far found to be true. So your question is equivalent to asking how the WEP leads naturally to a metric theory of gravity. However I don't think there is a simple and intuitive way to explain this. It seems obvious to us nerds, but rather less so to the non-GR heads.
One way of grasping the situation is to imagine two observers both starting at the equator and heading due north at constant speed. Because the surface of the Earth is curved the two observers will converge with each other (and meet at the North pole) even though both observers start parallel and just move in a straight line at constant speed. This is just due to the curvature of the Earth and the mass of the observers make no difference. The acceleration of the observers towards each other is given by the geodesic equation:
$$ {d^2 x^\mu \over d\tau^2} + \Gamma^\mu_{\alpha\beta} {dx^\alpha \over d\tau} {dx^\beta \over d\tau} = 0 $$
where the parameters $\Gamma^\mu_{\alpha\beta}$ are only dependant on the curvature of the Earth's surface. Note that the mass of the observers does not appear in this equation, and we wouldn't expect it to.
In motion on a sphere there are only two coordinates, longitude and latitude, but a metric theory of gravity extends the geodesic equation to three spatial and one time coordinate, as well as specifying how the parameters $\Gamma^\mu_{\alpha\beta}$ are related to any mass present. The result is that the four-acceleration is independant of the mass of the object, which is where we started.
Response to comment:
The geodesic equation applies to any metric theory. I introduced it to describe motion on the surface of a sphere, but it describes motion in curved spacetime just as it describes motion on a sphere. All you need is the correct form for the parameters $\Gamma^\mu_{\alpha\beta}$ used in the equation.
These parameters are called Christoffel symbols (of the second kind) and they can be calculated from the metric tensor. So if you're trying to describe how some object moves in spacetime the key thing is to find the correct metric tensor. And this is exactly what Einstein's equation does. It relates the metric tensor to an object called the stress-energy tensor that describes how matter and energy is distributed.
So the process is (1) work out the metric tensor using Einstein's equation, (2) calculate the Christoffel symbols and (3) solve the geodesic equation. That's what I mean by specifying how the parameters $\Gamma^\mu_{\alpha\beta}$ are related to any mass present.
I should note that in principle there can be any number of different metric theories of gravity, and they would differ from each other in step (1). General relativity uses the Einstein equation to calculate the metric, but you can have other theories using a different equation instead. However Einstein's equation turns out to be a very natural choice, and of course when we test it experimentally it gives the correct predictions. That hasn't stopped people suggesting other metric theories e.g. Brans-Dicke theory.
A: Let's start with the concept of an inertial frame: in such a frame, all laws of nature take their simplest form; in particular, an inertial frame is a frame in which Newton's Laws (or their Special-Relativistic equivalent) hold: an object on which no external force acts will either remain at rest or continue to move at a constant velocity. Any acceleration on the object is caused only by forces originating from external sources, not by the choice of frame (i.e. there are no fictitious forces).
This also means that all inertial frames are equivalent: the laws of physics are identical in every inertial frame, so there is no preferred frame of reference. Furthermore, Special Relativity tells us that all inertial frames should be moving at a constant velocity with respect to each other, because an accelerating frame would introduce a fictitious force. Finally, according to Special Relativity, any inertial frame can describe the entire spacetime.
However, gravitational fields cause a contradiction in Special Relativity. Take for example an astronaut who's inside a spacecraft with no windows and no boosters. Would the astronaut be able to tell if the spacecraft is orbiting the Earth, or orbiting another planet, or moving freely in outer space far away from any celestial object? No, a gravitational field has the same effect on every object inside the spacecraft. Everything in the spacecraft will be weightless, and the astronaut cannot conduct an experiment on board to determine where he is. As far as he knows, he might not be in a gravitational field at all. In other words, his spacecraft is an inertial frame.
But this leads to a contradiction in Special Relativity, because if you take two astronauts, each in their own spacecraft, then they will in general not be moving at a constant velocity with respect to each other (they could even be orbiting different planets), violating the property of inertial frames in Special Relativity.
The solution is that a gravitational field causes spacetime to curve: in a curved spacetime, inertial observers move on geodesics, which are a generalisation of straight lines in flat spacetime. On large scales, geodesics are curved paths, but on small scales a geodesic reduces to a straight line and Special Relativity holds to a good approximation. This means that inertial frames are only defined in small regions of space, where differences in gravitational fields are too small to have an effect. This solves the paradox: each astronaut resides in his own, locally defined, inertial frame. But there is no global inertial frame that connects them, so they do not move at constant velocity with respect to each other.
