> From each's perspective they should arrive at Earth first

What would happen if the winner grabbed a trophy (or whatever) on their way by? Relativity can break simultaneity, but not cause & effect. Thus "local" simultaneity must still be preserved in all reference frames. It's only distant events that different reference frames will disagree on.

> From each's perspective [..] the other would appear to not be moving at all

This would only be true if they're moving in the same direction. But in that case, they can't both be heading towards Earth.