Where does the idea gravity=curvature of spacetime really come from? I have been searching for quite a while but mostly found the answer: Einstein's genius. Quite unsatisfactory. I know and understand that the idea gravity=curvature of spacetime works. Furthermore I know that the starting point for Einstein's considerations was the equivalence principle. Nevertheless I can't make the connection from there, to why gravity is the curvature of spacetime. Any help or reference to where this is explained would be  much appreciated.
 A: Perhaps more of a comment that was too long, rather than an answer.

It seems a historical account for the motivation and construction of a derivation of the field equations,
$$R_{\mu\nu}-\frac{1}{2}g_{\mu\nu}R = 8\pi G \, T_{\mu\nu}$$
is probably what is required to answer your question. In 1913, Einstein published the entwurf equations which were covariant under general linear transformations; it was only much later did Einstein return to general covariance, and in fact had rejected such constructs in the past...
A historical account of every dead end Einstein faced, and how he eventually arrived at the Einstein field equations is a long story, too long for a physics S.E. answer. As such, I redirect you to Untying the Knot: How Einstein Found His Way Back to Field Equations Discarded in the Zurich Notebook, which is freely available here. If I recall correctly, the truth is Einstein wrote the correct field equations, but unknowning of their correctness, discarded them in his 'Zurich' notebook. The answer to your question (from Einstein's original perspective) almost surely lies within the text; in addition see http://arxiv.org/abs/1201.5353.
A: Since you mention the following in one of your comments

I'm less interested in Einsteins historical struggles and would love a
  more modern perspective on how to get to this insight.

I hereby unashamedly ignore history, and offer instead a quick plausibility argument.
Let's start with the equivalence principle which, loosely speaking, says that a (sufficiently small) system freely falling in a gravitational field is indistinguishable from the same system floating inertially in empty space.
Consider now a satellite freely orbiting the earth in a 2-D plane. Now use the vertical direction of the picture to embody time to form a spacetime representation, and in this picture plot the trajectories of the center of mass of each body.
Again roughly speaking, and using our eyes' geometry, you would draw the earth's world-line as a straight vertical line and the satellite's as a helix winding its way around this center line, right?
Now we try to reconcile this picture with the equivalence principle which, again, seems to suggest that each of these lines must be 'straight', because each object is really floating inertially.
They certainly don't look straight, but what if straightness means something non-Euclidean in spacetime? And that's where it would make sense to vary the geometrical stucture of spacetime in such a way that both trajectories really are geodesics of that non-conventional metrical structure.
Does that feel compelling enough to you?
Again, we are not pretending Einstein did this of course. Nor are we pretending that we could reconstruct general relativity easily from this argument. We are just making the connection plausible to a modern reader, rather than making it appear magically out of the blue.
A: First of all gravity is not the spacetime curvature, instead it is the geodesics assumed by a physical entity as it moves along the curved spacetime. What do I mean by geodesics? A geodesic is simply the shortest path a particle assumes in some paramitized curve. 
To understand the abovementioned think of a heavy ball on top of your bed or fabric, what would happen if marbles were placed near it? The genius of Einstein arises from his claim that gravity arises because of the curvature of spacetime, and not because of some mystic force field as Newton believed. Thus objects can assume intricate paramitized curves (Orbit of mercury), instead of the simple elliptic paramitized curve.
A: In "The Foundation of the General Theory of Relativity" Albert Einstein conducted two thought experiments - with a lift and with a spinning disk - where he compared gravity and acceleration. He considered a path of light as seen by an accelerated and a non-accelerated observer. As a result of his reasoning he concluded (at the end of the section 2):
"The path of a ray of light with respect to K' must in general be curvilinear, if with respect to K light is propagated in a straight line with a definite constant velocity."
A: The first motivation was perhaps the incompatibility of Newton's law with special relativity, which eliminated the idea of gravity being a force, and rather the geometric property of space and time, whose mechanism was curvature. Then, like @Yashbhatt said, it was the study of tensor analysis on curved manifolds initiated by Ricci and Riemann which led to the so called 'trampoline' analogy, which was perhaps the genesis of general relativity, and of course, it took Einstein's genius to realise that.
