How to find all planar squares with respect to the taxicab norm or the uniform norm? Excuse me if this is a silly question. Let $\|\cdot\|$ be any norm on $\mathbb R^2$. We say that four points $a,b,c,d\in\mathbb R^2$ form a square with respect to the norm $\|\cdot\|$ if $\|a-b\|=\|b-c\|=\|c-d\|=\|d-a\|$ and $\|a-c\|=\|b-d\|$. Conceptually, this means the four sides of the polygon with $a,b,c,d$ as vertices have equal lengths and so do the two diagonals.
How to characterize all squares w.r.t. the $1$-norm or the $\infty$-norm? It isn't hard to see that all "Euclidean squares" (i.e. squares w.r.t. to the Euclidean norm) are squares w.r.t. $\|\cdot\|_1$ or $\|\cdot\|_\infty$, but is the converse true?
 A: Your definition of square is somewhat problematic.  An example of a Euclidean square, by your definition, would be $ (0,0), (1,0), (0,0), (1,0) $.  However if you insist that the points be distinct, I think the definition works as intended.
Counter-example
However, $ l^\infty $ seems to admit some additional squares.  A set of examples is $ (0,0), (1,a), (0,a), (1,0) $ for $ -1 < a < 1 $.  This at least shows that not all $ l^\infty $ squares are Euclidean squares.  Moreover, since $ l^\infty(\mathbb{R}^2) $ and $ l^1(\mathbb{R}^2) $ are isometric (via the transformation $ l^1 \ni (x,y) \leftrightarrow (x+y, x-y) \in l^\infty $), anything we say about $ l^\infty $ squares carries over to $ l^1 $ squares.
Possible generalizations I don't think a proof would be terribly interesting, but I am fairly confident that every non-Euclidean-square $ l^\infty $-square (by the definition you gave) looks approximately like the set of examples I just gave, up to rescaling and 90 degree rotations.  If you really want to write down a proof, begin by noting that after translation, rescaling, and 90 degree rotations (and cyclic relabeling of vertices), any example of a square can be put in the standard position $ OPQR $ where
$$
O=(0,0), P=(1,\alpha), |\alpha| \leq 1
$$
Then one does some case analysis on the possible locations of $ Q $ which must be a distance $ 1 $ from $ P $, and hence must be on one of the four edges of the (square-shaped) sphere of radius 1 centered at $ P $.
Salvaging the conjecture You could thus salvage your conjecture if you additionally stipulate that squares be non-self-intersecting.  In that case, all $ l^\infty $ squares really would be Euclidean squares.  After selecting $ O = (0,0)  $ and $ P = (1,\alpha), |\alpha| \leq 1 $, the non-self-intersection assumption forces $ Q = ( 1 + \beta, \pm 1 ) $ where $ |\beta| \leq 1 $.  Assume $ Q = (1 + \beta, 1) $ without loss of generality.  Split into four cases by $ \alpha \leq 0 $, $ \alpha > 0 $, $ \beta \leq 0 $ and $ \beta > 0 $.  In each case we find we are forced by the restrictions to either take $ \alpha = \beta = 0 $ or $ \beta = -\alpha $, and in all cases we recover that $ OPQR $ is a Euclidean square.
