First message (main puzzle type):
"Let's send each other 'red' or 'blue' at random. The first time we send the same color, our next move is to end the game and announce that color. Send 'yes' as your next message if you agree to this strategy."
"Let's send each other 'purple' or 'green' at random. The first time we send the same color, our next move is to end the game and announce that color. Send 'yes' as your next message if you agree to this strategy."
The ability to send arbitrary messages and a logical human on the other end seem to make this trivial, but maybe I'm missing something.
In order to agree on a colour, you first must agree on a strategy.
In order to agree on a strategy, you first must agree on a strategy to choose the strategy.
In order to agree on a strategy to choose the strategy, you first must agree on a strategy to choose the strategy to choose the strategy.
...
Again, I think the "logical human on the other end" plus "arbitrary messages" along with the vanishing probability of constantly sending the same messages makes this easy in practice.
They're not asking to prove that it halts, but I get what you're saying.
Since the other party is just as logical as you, they can send you the same at the same time...
By the way, if you think this is an acceptable solution, then there's no need for the whole random colour and strategy thing; just send "The color will be red. Send yes if you agree to this". If you think this is not an acceptable solution, then neither is yours.
This problem is a variation of the distributed consensus problem in computer science. The canonical solutions (Paxos, Raft, et al) are non-trivial and there are unsolved corner cases. In short - this is problem where they are looking at your approach to problem solving rather than the solution itself.
But the other party could have informed you their strategy too. So you tell them "Let's use strategy X", and the same step you receive "Let's use strategy Y" from them. Looks like the first meta-task is to agree on a strategy :^)
The arbitrary message "constraint" seems to be an escape hatch.
But I think you could just use the same approach: "Every turn, keep suggesting a strategy until you receive the same strategy you suggest". Once that happens, then you both execute that strategy.
Both players are trying to collaborate here, so they'll naturally subordinate themselves on the first opportunity to win the game, they'll implement randomness or backoff naturally.