Whether you have the ROW or not, it is your responsibility to "see and avoid" even if the other pilot isn't. This is the aviation analog to defensive driving; call it "defensive flying".
There are no hard-and-fast rules for collision avoidance maneuvers. You basically have six options and their combinations, any of which will put you at a different point than you would be at the expected intercept (collision) point: climb, descend, turn left, turn right, speed up, slow down.
There was a study conducted by students at the University of Illinois at Urbana-Champaign, results available here, which might be helpful. The primary purpose of the study was to determine the usefulness of a computer traffic display in aiding the pilot to spot and avoid the traffic, but a secondary goal was to determine the most likely (and safest) collision avoidance maneuvers when presented with "intruders" on a collision course in each of 12 basic intercept paths (overtaking, crossing, or approaching, from the left or the right side, and climbing, level or descending). Among the lessons learned were:
Pilots (CFIs were used) were most likely to maneuver purely in the vertical to avoid traffic, moving opposite the vertical direction of the plane in sight and preferring to climb if the intruding traffic was holding altitude.
Despite the pilots' preference for the vertical, the maneuvers that cleared the "conflict" in the shortest time were in the horizontal plane, either turning opposite the plane's relative direction of travel to move behind, or slowing to let the traffic pass in front.
Pilots tended to do what was "easiest" at the time the conflict arose, especially if the intruder was sighted late (because the traffic didn't appear on the computer display; another of the variables they tested). Thus, single-axis maneuvers were most common (not counting the use of throttle to adjust power while performing a maneuver, such as cutting power to dive or increasing it to climb or turn).
Taking all this under advisement, the maneuver most likely to avoid a collision with another plane in otherwise clear skies is a level 30-45° turn in the direction of the intruding aircraft's tail, coupled with a reduction in airspeed if the intruder is on a crossing or approaching route (if he's coming up behind you, maintain airspeed). If the other pilot sees you and reacts at the same time, his most likely move will be a climb, which is fine; if he doesn't see you or react at all, you'll pass safely behind him at the same altitude hopefully avoiding his wake (if he's bigger than you).
However, there's some interesting game theory here. Any maneuver I tell you to make, except one, will keep you on a potential collision course if the other pilot reacts in the same way at the same time. As you supposed in your question, If you both climb, or dive, or speed up, or slow down, or try to turn behind each other, you'll crash (or at least get way too close for comfort). So, anything I tell you to do because it's unlikely the other pilot will do the same will be self-defeating, because eventually other pilots will do the same thing because it works.
The one move that won't result in a collision if mirrored is a 90° turn in the same direction as the intruder's movement across your vision. If he's on your left moving right, turn right 90°. If he's on your right, turn left. If the other pilot mirrors your maneuver, worst-case (an aircraft overtaking you directly from behind who turns the same way as you) you'll end up on parallel flight paths at whatever distance you first noticed each other. Best-case, you'll be heading away from each other and after a couple of minutes you can both reverse your turn and continue along your original heading.
But, this move is the worst thing you can do in several scenarios if the other plane holds its course. In high-offset crossing routes (close to 90°), turning away from the intruder will keep you out in front of him and probably too close for comfort, especially if he's faster than you (turning the crossing-route collision course into an overtaking collision).
Lastly, any formulaic maneuver we dream up in a two-plane scenario is going to break down when you add more planes, or restricted airspace, or weather. The maneuver may work in cross-country flight, but when dealing with merging Victor airways near a population center, there will be too many aircraft for any single avoidance maneuver to guarantee you'll get out of trouble without getting into more.
So, ultimately, your call.
