What does "the other's right" refer to in 14 CFR Part 91.113?
You wrote that:

it would seem both aircraft will either perceive themselves as being to the left or right of the other meaning either both aircraft or neither aircraft would have the right of way.

But that's only the case if the two aircraft are approaching head-on, or nearly so, and the FAR you quoted already accounts for that situation:

Converging. When aircraft of the same category are converging at approximately the same altitude (except head-on, or nearly so), the aircraft to the other's right has the right-of-way.  [Bolded emphasis mine.]

If the aircraft aren't approaching nearly or actually head-on, one aircraft will be unambiguously on the right:

As an extreme example, take the case of two aircraft &quot;approaching&quot; each other on side-by-side parallel courses in the same direction.  Obviously, in this situation, one aircraft will be on the right (and have the right of way).

(Red and blue are each a different scenario.)


Now consider two aircraft approaching each other on perpendicular courses (with a 90° angle between the two).  One aircraft's pilot will need to look to the left to see the other aircraft, and the other aircraft's pilot will need to look to the right to see the first aircraft.  The aircraft whose pilot has to look left is the aircraft on the right, and they have the right of way; the other aircraft is to the left of the first aircraft, and will have to give way.



Even if there's a 135° angle between the two aircraft's flightpaths, one pilot will still be seeing the other aircraft noticeably left of the center of their windscreen; this pilot's aircraft is on the right, and has the right of way.  The other pilot will have to look through the right side of their windscreen to see the first aircraft; the other aircraft is on the left, and has to give way.