What is wrong with violation of locality (EPR paradox)? When studying the EPR paradox, at some point we must resign ourselves that Reality and Locality can not be both true in the current theory of quantum mechanics.
A lot has been said in Physics.SE about the EPR paradox and about entanglement, but my question is quite different. To me, the violation of Locality doesn't look like a big deal: through entanglement you are not actually transmitting anything, neither physical quantities (energy, momentum,...) nor just information.
And indeed that form of violation of Locality doesn't contradict Special Relativity.
It really looks to me that nothing is being transmitted at faster than light speed. We are just gaining information about something which could even be at a space-like distance, but what is wrong with this?
Is there actually a theory that gets contradicted by this kind of violation of Locality? Any experiment? Or are scientists reluctant to give up on Locality just based on common sense and a classical view of the world?
 A: 
Or are scientists reluctant to give up on Locality just based on
common sense and a classical view of the world?

That's exactly it.
The EPR paradox is not really a paradox. It is explained by entanglement and by (the Copenhagen interpretation of) quantum mechanics. There is no transmission of anything, since there is only one wavefunction that spatially extends to encapsulate both bodies, and its collapse happens at the same time everywhere. So it's even a locality problem per se.
Also, in the usual EPR thought experiment, the probability of getting spin up or down is exactly 50-50, that is purely random. So you cannot even use this to transmit information. If the probability were not 50-50, then you must have had information about the particular decay process prior to the event...
The whole point of the "paradox" is that, classically, you expect things that are infinitely far apart from each other to be independent of each other. The whole question is "how far do the two bodies, that briefly interacted with one another at time 0, need to be in order to not require inclusion of the other one to describe the first?". Quantum mechanically, the answer is never.
A: 
We are just gaining information about something which could even be at a space-like distance, but what is wrong with this?

I think you're underselling the paradox a bit here. Of course you can imagine a classical situation wherein you gain information about an object space-like separated from you, in a way that would not surprise anybody. For instance, if you draw one ball from a bag with a red and blue ball, without looking at the color, and then travel to the Andromeda galaxy and look, instantly you also know the color of the other ball.
Bell showed, as a simple mathematical fact, that this is not sufficient to explain entanglement in quantum mechanics. One easy way to describe it is the CHSH game, where Alice and Bob (space-like separated throughout the game) are given independent random bits $x, y$ and they must output bits $a, b$ such that $a + b = xy \mod 2$. Classically it's not hard to convince yourself the best they can do is guess $a = b = 0$ and win $75\%$ of the time. But if they share an entangled pair of particles they can win $\approx 85\%$ of the time. This is much harder to come to terms with than the situation in the previous paragraph.
At the end of the day, sure, there's nothing wrong with this, and it has been conclusively demonstrated by experiments that this is really how the universe works. But it's definitely something surprising and counter to our classical intuition.
A: There is a computer analogy to explain QM that I do not think anyone will disagree. It is the computational version of quantum mechanics, that says that an entangled state in QM cannot be simulated by two separate computers that model each particle separately. That is, if you simulate two entangled particles that move away from each other, you cannot dedicate a separate computer to each particle, even if separated. For more details see here. In this sense, QM is non local. Many physicists, for some reason, still remain unconvinced that this computer analogy adds anything to the discussion. To me, it is a proof that non-locality is unavoidable.
A: 
We are just gaining information about something which could even be at a space-like distance, but what is wrong with this?

Nothing. Simply there are to points of view how to deal with entanglement. The usual is that the superposition is a temporarily but real thing, even over distance. And the entanglement is finished after production and only our knowledge about the components is zero until measurement. The complication comes from three fact that destroying the states but gaining the right result for both particles at less than 50 percent.
