Well, I dunno, if you describe physics as a Turing machine program, ala Solomonoff induction, special relativity may well be more incredible than god(s), chiefly because Turing machines may well be unable to do exact Lorentz invariance, but can do some kind of god(s), i.e. superintelligences. (Approximate relativity is doable, though).
Solomonoff induction creates models of the universe from the point of view of a single observer. As such, it wouldn't probably have any particular problem with Einstenian relativity.
On the other hand, if you want a computational model of the universe that is independent from the choice of any particular observer, relativity will get you into trouble.
Another monthly installment of the rationality quotes thread. The usual rules apply: