"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.