Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

We will prove this statement using contradiction.

For the sake of contradiction, assume that for some $n$, a rook can color all cells in $2n-2$ or less moves. 

We call a move a 'row move' if the rook goes from one cell to another one in the same row. 'Column move's are defined similarly.

If the rook makes a move from one cell in a row/column to another in the same row/column, we say that the row/column is 'good' and 'bad' otherwise. The rook can only make one new row/column good in every move. So, there are at least two bad row/columns.

Assume that a row and a column is bad, then the cell at their intersection cannot be reached by the rook from any other cell. So, the intersection cell is the one the rook started on but in that case the rook cannot move.

So, there are either at least two bad rows or two bad columns. Without loss of generality, there are two bad rows. At least one of these is different from the one the rook started on. So, the rook must have reached the $n$ cells in this row from the $n$ columns. Which implies that all columns are good. So, there are at least $n$ column moves. The rook has to move between columns using row moves. It starts in one column, and it needs to make at least $n-1$ row moves to reach the $n-1$ other columns. So, the rook needs at least $2n-1$ moves in total and that is a contradiction.

So, the rook needs at least $2n-1$ moves to color all the cells in a $n\times n$ grid.