In a mathematical sense, special relativity is not particularly difficult. Undergraduate physics students often learn it by year two as it doesn't require much more than calculus and linear algebra. That's not all to downplay Einstein's genius. If it weren't him, I'm sure others would've gotten there eventually, but he was the first there, and his insights were primarily physical (assuming both the constancy of the speed of light in all reference frames and that the laws of physics are the same in all inertial frames of reference).

General relativity was much more difficult. It took Einstein about a decade to develop it and he had to learn differential geometry in order to do so. This work was undoubtedly more profound and required much more advanced mathematics merged with deep insights such as the equivalence principle [0]. This was what made Einstein so successful: the combination of mathematics with physical insights that no one else had put together at the time.

[0] https://en.wikipedia.org/wiki/Equivalence_principle

When it comes to physics, I think the issue is more that we are on the limit of what we can reasonably test. It's like trying to figure out how the body works before the invention of the microscope.

Newton's Gravity was known to be incomplete for many years, just by looking at Mercury. It took several carefully derived experiments studying light for 100s of years that led us to Maxwell's equations in the 1860s that became the basis for Einstein's special relativity in the 1910s. You don't need a billion dollar particle accelerator to come up Maxwell's Equations (2 of them were done by Guass in the 1700s!). 20 or 30 years (and talent!) studying calculus or physics could get you something.

Today we know Einstien's theory of gravity is incomplete but the only places it is incomplete is inside of a black hole (good luck running a test in a blackhole) or at very tiny scales where gravity's affect is minimal. Today, I don't know how you would even come up with a competing theory without having millions to spend on a particle accelerator. While einstein famously just did a thought experiment on what should happen if the speed of light is constant for all observers, most "discoveries" are done now by smashing particles in billion dollar tubes.

> good luck running a test in a blackhole

Theoretically speaking, it's not that hard to run a test inside a black hole (getting to one is the hardest part that we know of). It's communicating the results to anyone else that's "slightly" harder.

Jokes aside, in physics we have both a problem with what can be tested, but also one on the theory/mathematics side. Even for a relatively technical problem, we don't have any good way of solving the actual equations of any slightly complex system in either GR, QM, even Newtonian mechanics. We are actually always relying on numerous approximations and simplifying assumptions, and some of these could themselves lead us astray in some cases.