I just want to be clear it took an actual space agency 11 years to pull this off and the company I interviewed at just backed up data for people.
Assuming Mars is featureless (if it has features, they can both climb Olympic mons, for instance, as Mike Ash already said) and they cannot leave Mars (if hey do, they could have agreed before to meet in a bar in, say, Paris), the solutions I can think of all are a bit impractical:
- both dig a hole to the center of Mars and wait there for the other to arrive.
- both spread themselves out over half the area of Mars.
- both self-replicate until they cover the surface.
- at least one of them starts annihilating Mars.
If they are allowed to discuss strategy beforehand, the following will work:
Both walk straight ahead along a great circle. When (not if; great circles cannot not intersect and not be the same) they meet the trail of the other, the slower one stops at the intersection, and waits for the faster one to return on its path.
It should be possible to move a few larger rocks, maybe? Spirit, Opportunity and Curiosity have robotic arms. Good image processing might or might not recognize patterns in the stones.
(http://nssdc.gsfc.nasa.gov/image/planetary/mars/vikinglander... for an example what most images I saw look like. I imagine it looks like this after a storm: http://nssdc.gsfc.nasa.gov/image/planetary/mars/vikinglander...)
(Of course, compared to mikeash's answer, this is overengineering and only applicable if their conditions are not met (prearranged meeting point; we have a map and know our location))
This seems too easy. Did I miss something?