Here is the sketch of an argument that I heard from Martin Balko. 

It seems to show that the correct asymptotics is $N(k) = k^2 / polylog(k)$. That is, there is a B/W coloring of the $N(k) \times N(k)$ grid such that some permutation of size $k$ is not contained in either the B or the W sets. If true, then this is quite close to the upper bound of Ben Barber from the other answer.

The argument uses a result from the recent paper **Ordered Ramsey Numbers** by Conlon, Fox, Lee, and Sudakov (http://arxiv.org/abs/1410.5292).

**Theorem 2.4** of the paper claims (essentially) the following.
For all $k$, there is some value $N = k^2 / polylog(k)$ and some perfect matching $M$ of a bipartite graph with vertices $L = \{1,...,k\}$, and $R = \{k+1,...,2k\}$, such that we can color B/W the edges of a complete graph $H$ with vertices $\{1,...,N\}$ such that $M$ is not _contained_ either as a B-subgraph, or as a W-subgraph. Here, ``contained'' means that the vertices of $M$ are mapped to vertices of $H$ such as to respect the ordering.

Our problem is essentially the same, with the difference that $H$ is a complete _bipartite_ graph with vertices, say $\{1,...,N/2\}$ and $\{N/2+1,...,N\}$. This can be seen as deleting some of the edges of $H$, or coloring them with some third color that we can not match to anything. Denote the resulting graph as $H'$. If some matching was not contained in $H$, then it is also not contained in $H'$, i.e. by going from the complete to the complete bipartite graph, avoiding some subgraph becomes easier. 

Note: $H'$ plays the role of the matrix, and the ordered matching $M$ plays the role of the contained (or avoided) permutation.

It would be nice to get some intuition how such a coloring looks "visually" -- from the proof in the paper it is hard to get such an intuition.