For the toroidal case, it is clear the statement of the problem is referring to the cells of a $\mathbb{Z}_{N} \times \mathbb{Z}_{N}$ lattice on the surface of the torus, labeled with the numbers $1,2, \ldots, N^{2}$, where one has to determine the least possible maximal absolute value $M$ of the difference of labels assigned to orthogonally adjacent cells.

The toroidal $N=2$ case is trivially seen to be $M=2$ (thus coinciding with the planar case).
!

The unique $2 \times 2$ toroidal array.

For $N \geq 3$ we will prove that value to be at least $M \geq$ $2 N-1$. Consider such a configuration, and color all cells of the square in white. Go along the cells labeled 1, 2, etc. coloring them in black, stopping just on the cell bearing the least label $k$ which, after assigned and colored in black, makes that all lines of a same orientation (rows, or columns, or both) contain at least two black cells (that is, before coloring in black the cell labeled $k$, at least one row and at least one column contained at most one black cell). Wlog assume this happens for rows. Then at most one row is all black, since if two were then the stopping condition would have been fulfilled before cell labeled $k$ (if the cell labeled $k$ were to be on one of these rows, then all rows would have contained at least two black cells before, while if not, then all columns would have contained at least two black cells before).

Now color in red all those black cells adjacent to a white cell. Since each row, except the potential all black one, contained at least two black and one white cell, it will now contain at least two red cells. For the potential all black row, any of the neighboring rows contains at least one white cell, and so the cell adjacent to it has been colored red. In total we have therefore colored red at least $2(N-1)+1=2 N-1$ cells.

The least label of the red cells has therefore at most the value $k+1-(2 N-1)$. When the white cell adjacent to it will eventually be labeled, its label will be at least $k+1$, therefore their difference is at least $(k+1)-(k+1-(2 N-1))=2 N-1$.
!

Example of coloring the array.
The models are kind of hard to find, due to the fact that the direct proof offers little as to their structure (it is difficult to determine the equality case during the argument involving the inequality with the bound, and then, even this is not sure to be prone to being prolonged to a full labeling of the array).

The weaker fact the value $M$ is not larger than $2 N$ is proved by the general model exhibited below (presented so that partial credits may be awarded).

A general model for $M=2 N$ in a $N \times N$ array.
By examining some small $N>2$ cases, one comes up with the idea of spiral models for the true value $M=2 N-1$. The models presented are for odd $N$ (since 2011 is odd); similar models exist for even $N$ (but are less symmetric). The color red (preceded by green) marks the moment where the largest difference $M=2 N-1$ first appears.
[1] Also see Sloane's Online Encyclopædia of Integer Sequences (OEIS), sequence A001222 for $\Omega$ and sequence A008836 for $\lambda$, which is called Liouville's function. Its summatory function $\sum_{d \mid n} \lambda(d)$ is equal to 1 for a perfect square $n$, and 0 otherwise.
Pólya conjectured that $L(n):=\sum_{k=1}^{n} \lambda(k) \leq 0$ for all $n$, but this has been proven false by Minoru Tanaka, who in 1980 computed that for $n=906,151,257$ its value was positive. Turán showed that if $T(n):=\sum_{k=1}^{n} \frac{\lambda(k)}{k} \geq 0$ for all large enough $n$, that

TABLE I: The spiral $3 \times 3$ array.

TABLE II: The spiral $4 \times 4$ array.

TABLE III: The spiral $5 \times 5$ array.

TABLE IV: The spiral $7 \times 7$ array.