Why was pseudo-Euclidean geometry not enough for general relativity? How would you explain to someone the change that Einstein needed in geometry for his new ideas about gravity and spacetime, what did he seek but could not be described by pseudo-Euclidean geometry? 
Assuming you're talking to a highschool student who only knows Euclidean geometry, Newtonian physics, Calculus and Cartesian analytic geometry
Edit. So gravity is the reason that geometry of space can't be Euclidean (correction: this is not quite right, as explained by 2 users). I want to ask more specifically, how? Basically I was expecting answer that contrasts the old gravity (wasn't it just a vector field?) and the new gravity (something more complicated)? Einstein found the old geometry somehow insufficient to describe his new idea about gravity, I want to know more about this part. 
Edit 2. I think I'm getting close to an understanding from piecing together various answers. So in the Newtonian picture of gravity: 


*

*There's an issue with action at distance (which seems like a huge problem after the postulate about speed of light was made) 

*There's also another issue with tidal gravity in a reference frame
free falling in gravitational field (in such frame, you can't transform gravity away if space is described by Euclidean geometry because if you could you'd have two objects initially at rest with zero proper acceleration moving towards each other, or, two parallel straight lines intersect)


In Einstein's picture, space is like a trampoline surface, when empty, it's flat, you put a ball on it, the ball curves the surface and the distortion is local and spreads at speed c. Furthermore you can treat gravity like a fictitious force in a free falling frame: two objects initially at rest with zero proper acceleration just follow their geodesics.
But the answer I have been looking for since the beginning is more quantitative than the above. 
I'm looking for an explanation that starts with the Euclidean geometry/Cartesian coordinate description of gravitational field, and ends with differential geometry/metric tensor field/(something else ?) description. 
I still have a lot of fog about this part but I think I read somewhere that Einstein had some struggles when he needed to describe gravitational field as a mathematical object with 10 components, also what is its connection to coordinate free differential geometry? I want to know more about these points.
 A: 
How would you explain to someone the change that Einstein needed in geometry for his new ideas about gravity and spacetime, what did he seek but could not be described by pseudo-Euclidean geometry?

First, we need to make sure that you understand how motion and acceleration without gravity works in pseudo-Euclidean (flat spacetime) geometry before we can explain why pseudo-Riemannian (curved spacetime) geometry is required to describe gravity. 
In flat spacetime an object which is experiencing no forces will travel in a straight line at constant speed, as dictated by Newton’s first law. In a spacetime diagram this is simply a straight line. In contrast, an object which is subject to a force will accelerate, which is represented by a curved line in spacetime. The radius of curvature of this line is directly related to the proper acceleration with a sharper curve corresponding to a greater proper acceleration. Proper acceleration is the physical acceleration directly measured by an accelerometer so this relationship is very convenient and has a direct experimental significance. 
Now, parallel lines in spacetime correspond to objects at rest with respect to each other. And straight lines in spacetime correspond to objects with accelerometers that read 0. So, two parallel straight lines are objects that are at rest with respect to each other and whose accelerometers read 0. They will never collide. 
However, in the presence of tidal gravity this no longer holds. With tidal gravity two objects can initially be at rest (parallel) and have zero proper acceleration (straight lines) but still collide (e.g. as they fall through holes drilled to the center of a planet). This is geometrically impossible in flat spacetime, but is possible in curved spacetime. 
Consider the surface of a sphere: the concept of straight lines generalized to what is called a geodesic and on a sphere the geodesics are great circles. Longitude lines are geodesics, so they qualify as straight lines in a curved space (a sphere). So consider two nearby longitude lines, at the equator they are parallel but they intersect at the poles. 
So this is exactly what we need to describe tidal gravity: curved spacetime (pseudo-Riemannian geometry). Therefore, tidal gravity will be represented by curved spacetime, inertial objects having accelerometers reading 0 will follow geodesics, and such objects may be parallel (at rest) at one point and later collide. 
A: While general relativity (the theory including gravity in the description of spacetime) needed to use something different to Euclidean geometry, special relativity, which was there before, also needed it.
The major change in special relativity is how space and time are related to each other. The geometry of space itself is still Euclidean, and only the joint description of space and time is what breaks that. This can be seen as a necessity coming from the fact that there is a speed limit for particle propagation.
In general relativity, you also have that. Nevertheless, the inclusion of gravity might result in the spatial part not being Euclidean. Gravitational fields are described by the theory as a change in spacetime. When there is not a gravitational field, spacetime is identical to that in special relativity. But the inclusion of matter, light and different forms of energy in the Universe creates gravitational fields which modify spacetime, in some cases taking it far from being pseudo Euclidean.
A: Einstein wanted a better explanation than Newton gave for why objects with different masses, like an apple and a cannonball, fall at the same rate. His explanation is that the rate at which objects fall has nothing to do with their mass... it has to do with how spacetime is curved. Both objects just follow the same “straight line” through curved spacetime. This explanation can’t work in Euclidean space because straight lines there are too simple.
A: As I said in a comment, Einstein realised that a geometrical model that explained gravity as intrinsic spacetime curvature solved the action at a distance problem of Newtonian gravity. With Minkowski's help, he realised that in Special Relativity there is a fundamental geometrical relationship between space and time. And once he had the insight that gravity could be treated as a fictitious force in a curved spacetime, it was only natural to use non-Euclidean geometry.
Of course, it's possible to use flat geometry when working with a curved space, but it gets ugly. Imagine trying to navigate large distances on the Earth using XYZ coordinates instead of latitude & longitude. I doubt that navigators in the time before computers would have been happy with that. ;)
Another important issue is that to work with a curved space in Euclidean geometry you need to invoke an extra dimension (or two) that the curved space is embedded in. It's both physically and mathematically cleaner if we can avoid requiring such extra dimensions, and Riemann showed us how to do that. On a related note, General Relativity gives us the freedom to choose whatever coordinates are convenient for a particular problem, rather than having a particular system of coordinates imposed on us. After all, the universe doesn't come with an absolute system of coordinates, and so a physical theory should reflect that.
