It's not random; it's a superposition.

It is perhaps less nonsensical (in a "common sense" way) to think of it in terms of the many-worlds interpretation. The moment you have created the photons, you have forked the universe - but observers on both sides are still identical in both worlds, because they haven't done anything that'd allow them to figure out which universe they're in. So for each observer, we treat both "versions" of that observer as one and the same.

Now, when one of the observers measures their photon, they figure out which fork they're in. And then in that universe, the other observer measuring it will also get the same result, of course, proving that they're also in that same universe. And in the other universe, the second observer will get the opposite result, again, proving that they're in that other universe. But neither measurement actually caused anything to happen, nor did they get any information about the opposite observer in their universe as a result of it.