I think the real difficulty is in human language. "a ^ ~a is a contradiction" is still perfectly applicable but apparently requires a "for observer A" clause. To supply all of the clauses necessary to make a completely unambiguous statement would be way too long to be humanly comprehensible. It makes me think of the Carl Sagan quote about needing to invent the universe before you can make anything "from scratch".

I'd argue that "event A happens before event B" is objectively true if and only if event A happens in event B's past light cone, and so there's no actual contradiction. The only weirdness you get is that if events A and B are space-like separated, none of the statements "event A happens before event B", "event A happens after event B", or "event A happens at the same time as event B" are objectively true. But you wouldn't say it's contradictory or paradoxical, just that it's a partial order rather than a total order.

You're simply misrepresenting what the actual statement with a truth value is in these cases. The fact that events happening close to each other temporally from fast-moving inertial frames can't be given a canonical temporal ordering doesn't undermine the existence of truth. A happens before B in the inertial reference frame of one observer and B happens before A in the inertial reference frame of a different observer are both true statements, and the converse of each is a false statement. The insight of special relativity is that there exists no God's eye reference frame independent of inertial reference frames. Nothing moves against some eternal static backdrop serving as a coordinate anchor. Things only move with respect to other moving things. That is in and of itself also a true statement, and the converse is false. Non-contradiction still holds everywhere. That you need further details and context to determine the truth of a statement doesn't mean it has no defined truth value.

The Special Relativity example you brought up is not a good example because it's about observation, not the truth of the order of the events.

Reality is not dependent on the observer, but we are observers, so that's why everyone thinks they have their own version of the truth. We are the weak link.

>Nature does not appear to be at all bothered by this "contradiction"

There is no contradiction. Our intuition for what 'A happens before B' means and implies is just bad/incomplete, as special relativity models.

>Even more puzzling "contradictions" arise in quantum mechanics.

I would bet a couple years of wage that what seems like contradictions will eventually be cleared up with some non-intuitive models, just like with special relativity.

I imagine the 'changes based on observer' problems of quantum mechanics will be more understandable once we decide what an observer is ( goddamnit people from physics, you don't add such a highly abstract variable to your model without giving it some good definition x( ), with some better experimental apparatus or with some deeper models of reality.