Coloring a $9\times9$ Board
Tile the plane with copies of the $4\times4$ pattern
$$\pmatrix{0&0&0&1\\0&0&1&0\\1&0&1&1\\0&1&1&1}$$
(using, say $0$ for Black and $1$ for White). Then any $9\times9$ subarray will contain the $16$ different $2\times2$ patterns exactly $4$ times.
The essential idea here is to identify opposite edges of the $4\times4$ array, making a torus out of the square. It's a bit laborious, but not all that hard, to check that the $16$ different $2\times2$ patterns occur exactly once. Four copies of it, therefore, again with toroidal identification of edges, contain the $16$ patterns $4$ times each. Buffering four copies with an extra row and column simply makes the toroidal identification explicit.
Remark: Peter's $9\times9$ solution is not of this "toroidal-based" form.
[0 1 0 0 1 1 0 0 0]
[1 1 1 0 1 0 1 1 1]
[1 1 0 1 0 0 0 0 1]
[1 1 1 1 0 0 1 0 0]
[0 1 0 1 1 1 1 1 1]
[1 0 1 0 1 1 1 0 0]
[0 0 1 0 0 0 0 0 1]
[1 0 1 0 1 0 0 0 1]
[0 0 0 1 1 0 0 1 0]
should be a coloring satisfying the condition! Can someone verify it ?