Many people regard Einstein as having done greater work than Newton.

When making "top ten" lists of physics, usually Newton, Einstein and Maxwell are among the top three physicists of all time. But such lists are in general dubious; for one thing, Einstein needed the results by Newton and Maxwell to do his own work. Beside, the three worked in very different periods of time with different problems facing physics.

What makes Newton unique, is that Newton would in general make the top ten list of all time great mathematicians. Usually the top three would be Archemides, Newton and Gauss. But again, such lists should not be trusted. If you want to rate scientists, learn what they did, and make your own (subjective) rating.

So it's worth noting that a few people are now claiming that relativity is either derivable from Newtonian physics or wrong.

There has always been people claiming Einstein was wrong, often because Einstein's theory are strange to "common sense". And it is well known that you can make any theory fit all available experimental results by making ad hoc extensions to the theory. It is worth nothing that Newton himself would probably not have liked the extensions necessary and Newton himself found parts of his own theories lacking.

Some physicists seem to prefer complicated explanations over simple ones.

This is where you are wrong. Einstein's theories are much simpler than Newton's. To make Newton's theories and Maxwell's theories fit, you need an "ether" with very strange and peculiar properties. This was the state of physics when Einstein came along. And you need to add even stranger properties to fit what has been learned since Einstein.

What Einstein did was to show that you could make a nice unified theory of Newton and Maxwell and get rid of this complicated, ad hoc concept of an ether, but you would have to change your concept of time and space in the process. So, Einstein theory of relativity passes the test of Occam. Einstein's theories are much simpler mathematically and physically than any theories that try to preserve Newton's laws and still fit known experimental facts. The only price to pay, is that common sense about time and space has to be updated.