Rather than looking at the wiring from the perspective of the current/old switch conenctions, lets look at it from the perspective of the wiring in the walls.

One cable in each box will have three colored wires, plus bare copper ground. They will be Black, White and Red. Look into the box and figure out which Black wire goes into the same cable sheath as the Red. That is the 'three-way' cable. Mark that Black with a bit of tape wrapped around the insulation.

Do the same at the other box, and also flag that Black-that-runs-with-Red wire with tape. Now you have identified both ends of the three-way cable in the wall, and importantly which Black wire is part of that cable.

In one of the boxes, the remaining un-flagged Black wire will be the power feed from the electrical panel.

In the other box the remaining Black wire will be the one that feeds the actual load (the cable to the light).

You need to figure out which box has the Black wire that is the power feed, and which has the Black wire to the light. Mark the power feed wire with a different bit of tape, marked 'power feed'. Mark the Black wire in the other box with the label 'to light'.

Once that is sorted out, you can match the wires to the wiring diagram for your new switches.