Do you want $r \geq 2$? Otherwise take $G$ to be a single matching with the `edge endpoint reversing' automorphism.

Excellent, this means I don't have to construct that argument myself. The basic idea must be this -- we have a 'state' which consists of the first empty square plus the next u+v (plus or minus one) squares. The greedy tiling gives a transition between states. If this is invertible, i.e. we can read the old state from the new one, then the first repeated state must be the initial state (of all empty squares), and hence we will have covered an initial segment.

Further to my previous comment concerning (3). I just did a long overdue experiment and can report that for 0 <= u, v <= 30, gcd(u,v) = 1 (obviously the only case we need to worry about) and u + v <= 30, the answer to (3) is yes. Moreover, the method of the standard solution (greedily use tiles of one type so long as you can, and whenever necessary use one of the other type) seems to produce such a tiling. The worst case in this range was u = 9, v = 20, which required 1638 tiles before tiling an interval.

As the author of the original problem I can add a spot of historical data. I believe the problem arises out of a result mentioned in Golomb's book on Polyominos (which regrettably I don't have access to just at the moment to check). I think the answer to (1) is definitely yes using a finite state automaton argument. Obviously yes to (3) implies yes to (2) (if I'm reading it correctly), and I also believe the answer to (3) is yes, but have never quite managed to convince myself of that.

@alex Sorry, stupid misreading of the question on my part.

Regardless of n/k it seems to me that the most likely optimum is where each randomly picks a set of size $\lfloor n/2 \rfloor$. If everyone is always picking sets of the same size, then they lose only when two of them pick the same set, so it makes sense to have as many sets available as possible.

Good point about the 1D impartial version. I might follow that up later today. One further thought (pertinent to the original version as well), in the case where (x+y)/2 is not in the lattice it might be interesting to allow the mover to choose which nearest lattice point gets marked.

It seems to me that the colouring could be a bit of a distraction. That is, why not consider the impartial game (where we can choose any two distinct points whose "midpoint" is not yet marked, and add the midpoint). Since every point in the rectangle will now be accessible, the game will certainly end, and the issue becomes whether it is a first or second player win.