Largest sphere in a "grid graph" Let $G=(V,E)$ be an undirected graph, such that $V$ is a subset of
$\{1,\dotsc,N\} \times \{1,\dotsc,N\}$ and there is an edge between $2$ vertices if and only if they have one identical coordinate and differ by exactly $1$ in the other coordinate (we can think about it as a grid, with some points omitted, such that we can move up/down/right/left).
The graph $G$ defines a metric (by $d(v_1,v_2)=$minimum number of edges in a path from $v_1$ to $v_2$).
A sphere is defined as usual: for $v \in V$, we let
$S(v,r)=\{u \in V \mid d(v,u)=r\}$.
What is $\max\limits_{v,r}|S(v,r)|$? An asymptotic expression in terms of $N$ would be enough. I strongly suspect it is $O(N)$ because that is what we get if $V=\{1,\dotsc,N\} \times \{1,\dotsc,N\}$ (i.e: no point omitted) and take $v=(N/2,N/2)$ and $r=N/2$.
 A: It is possible to achieve a sphere of size $O(n^2)$ by using "the H fractal".
Define
$$V=\left\{
(x,y)\in\{1,\ldots,N\}\times\{1,\ldots,N\}
{\ \Huge|\ }
\begin{aligned}
2\mid x \ \ \wedge\ \ l(x)+1 \in g(y) \\
or\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,\,\\
4\mid y \ \ \wedge\ \ l(y) \in g(x) \ \ \ \ \ \ \ \,\,
\end{aligned}
\right\}$$
where $g(n)$ is the set of $k$ for which the binary "$2^k$s" and "$2^{k+1}$s" digits of $n$ differ, and $l(n)=\mbox{min}(g(n))$.
Here is a picture for $N=15$.
   . . . . . . . # . . . . . . .
   . # . . . # . # . # . . . # .
   . # . . . # . # . # . . . # .
   . # # # # # . # . # # # # # .
   . # . # . # . # . # . # . # .
   . # . # . # . # . # . # . # .
   . . . # . . . # . . . # . . .
   . . . # # # # # # # # # . . .
   . . . # . . . . . . . # . . .
   . # . # . # . . . # . # . # .
   . # . # . # . . . # . # . # .
   . # # # # # . . . # # # # # .
   . # . . . # . . . # . . . # .
   . # . . . # . . . # . . . # .
   . . . . . . . . . . . . . . .

The size of a large sphere centered at the top, when $N$ is a power of 2, is $N^2/16$.  Considering the connectivity as $N$ grows, we can see that for all $N$, there is a sphere of size at least $N^2/36$.

(The problem with "the Plus fractal" (underlying Joriki's very nice animations) is that although it is space-filling, the nearest of the four pluses (not drawn in those animations) is closer than the other three and so does not contribute to the sphere.  The H fractal doesn't have this problem because the route to any part of the H starts by going to the center.)

[added by joriki]
Here's an animation for this very nice solution – as with the others, you can right-click to open it in a new window in full size or open it in Mac OS Preview to browse the individual frames at leisure.
very nice solution http://home.arcor.de/joriki/hfractal.gif
A: I'm leaving my original $N^{\log_23}\approx N^{1.585}$ construction below since it's easier to understand and verify, but I've found an improved $N^{\log_2(3+\sqrt{17})-1}\approx N^{1.833}$ construction:

I've increased the time per frame to $2$ seconds to make it easier to see the principle. (By the way, Mac OS Preview allows you to browse through the individual frames with the cursor keys if you download the image.)
Here's a static image of an intermediate stage:

Each branch brings forth $3$ branches of the next generation and $2$ of the generation after that, so the growth is determined by the recurrence
$$a_{k+2}=3a_{k+1}+2a_k$$
with characterstic values $(3\pm\sqrt{17})/2$. Thus, the number of points is $\sim k^{(3+\sqrt{17})/2}$ for $N=2k+1$, so $\underset{v,r}{\max}|S(v,r)|$ is $\Omega(N^{\log_2(3+\sqrt{17})-1})\approx \Omega(N^{1.833})$.
Here's a not quite rigorous argument that the number is in fact $\Omega(N^{2-\epsilon})$ for any $\epsilon>0$. Looking at the later stages of the constructions, you see areas that don't get filled. The reason they don't get filled is that they're close to points that are reached early and it would be more complicated to "waste enough time" to get to these areas late enough -- one would have to add paths that go back and forth a couple of times and then sprout out into these areas. But the "cost" of going back and forth a certain number of times, the number of points used up by such paths, is linear in $N$, whereas the area that can be filled using them is quadratic in $N$. So it may not be possible to efficiently fill all the small holes that are left by the final stages, but for any given pattern of paths leading into the empty areas, it can be applied at all stages except for the last $s$ stages, where $s$ depends on the "thickness" of the pattern. But these $s$ stages only give us a constant factor of $4^s$ in the number of points; we can simply drop them without changing the asymptotic dependence on $N$. So we can keep building more and more complicated paths into the empty areas, and the cost of using up a few rows of points will asymptotically not matter since the number $s$ of stages at which it becomes impossible to lay those paths is independent of $N$ whereas the number of stages at which the cost of the paths is negligible compared to the areas opened up by them grows with $N$. I believe this shows that the number is $\Omega(N^{2-\epsilon})$ for any $\epsilon>0$, though it might be a bit tedious to spell the argument out rigorously.
Here's the original $N^{\log_23}\approx N^{1.585}$ construction:

Here's a static version:

The images are being scaled down to fit the column width; you can open them in a new tab/window to get the full resolution (by right/ctrl-clicking).
All the bright points at the ends of the segments are at the same distance from the centre. Some of these are reached in different ways; I counted the number of distinct points while drawing the frames. Counting from $k=0$, and not counting the initial frame with $4$ points, there are $4(3^k+2^k)$ distinct points in the $k$-th frame, with $N=2^{k+1}+1$, so we have
$$\underset{v,r}{\max}|S(v,r)|>4\cdot3^{\log_2(N-1)-1}>3^{\log_2(N-1)}\sim3^{\log_2N}=N^{\log_23}\;.$$
I suspect that the number is also $O(N^{\log_23})$, but I haven't found a proof yet.
P.S.: I just realized that the construction was unnecessarily complicated -- almost the same figure can be constructed in a more straightforward way, which avoids points being reached twice and makes it obvious that the number of points is being tripled in each step:

(Again, right/ctrl-click on the image and open it in a new tab/window to get the full resultion -- it looks much nicer :-)
Here the number of points in the $k$th frame is simply $\frac433^k$.
P.P.S: I just realized that since there's automatically an edge between adjacent points, we actually need to double $N$ to be able to realize only the connections shown in the images; but that's just a constant factor so it doesn't change the $\Omega(N^{\log_23})$ conclusion.
A: Added. I greatly misunderstood and misjudged the question. As @Jyrki points out, the set $V$ is relevant to the problem (and without it, the question, just like my answer, becomes trivial), the distance between $(x_1, y_1)$ and $(x_2, y_2)$ is not $|x_1 - x_2| + |y_1-y_2|$, and so on. I am just keeping the answer for the records. 

A wrong attempt.
I hope I understood your question correctly. I do not see how $V$ is relevant to the problem. 
We'll prove that any sphere is indeed of size $O(N)$. Fix any center $v = (v_1, v_2)$ and a radius $0 \leq r \leq 2N-2$. (The upper bound $2N-2$ is the diameter of the graph.) The sphere $S$ is defined to be the set of points $(v_1+x,v_2+y)$ such that $|x| + |y| = r$. Clearly, $-r \leq x \leq r$; moreover, for any value of $x$, there are at most $2$ possible values of $y$, namely $\pm(r-|x|)$. So, the total number of points is at most $$\sum_{x=-r}^r 2 = 2(2r+1) \leq 2(4N-4+1) = O(N) .$$ 
