For each of the $4n^2$ cells, draw a line to two other cells, the partner cells on the top and bottom layer (i.e. belonging to the same lego). Since the building is connected, the lines form a hamiltonian cycle. At the corners this cycle must form an "L-shape". Note you have to visit corners in a cycle, by this I mean the 8 lines from a corner must appear on the hamiltonian cycle in order, either clockwise or anticlockwise. The proof of this is a bunch of cases, where the contradiction arises from being unable to visit some other corner (I'm on phone so lazy type). Now colour the grid checkerboard. Legos on the bottom layer all start on the same colour. Hence, we are done.

Official Solution: Let the graph corresponding to the first and second layer to be $G_1=(V, E_1)$ and $G_2=(V, E_2)$, respectively, where each edge connects two adjacent squares tiled by a $1\times 2$ block. Notice that $V$ is the same for both graphs (the $4n^2$ nodes), and each node in $V$ has degree 1 in both cases. If the same edge $e$ appears in both $E_1$ and $E_2$, then this $1\times 2$ block is isolated and therefore cannot be connected. It then follows that $E_1$ and $E_2$ are disjoint. Now consider the graph $G_3=(V, E_1\cup E_2)$, i.e. each node is 2-regular. Since we're given that $G_3$ is connected, this graph must be a single cycle. Let's claim the following: if we traverse the cycle in certain order, then it must all pass through the four corners in the same orientation (i.e. all clockwise, or all anticlockwise). Indeed, suppose that we traverse the bottom left corner in the following order as in the figure below: Consider the moment where the path crosses the bottom right corner. Then this part of the path, together with the bottom boundary, separates the any possible squares in between from the rest of the grid. In particular, if there is any such square in the bottom layer, it will be separated from the rest of the grid. Since we can only travel through the rest of the grid until we return to the bottom left corner, it follows that all the squares in the bottom layer must be part of the path from bottom left to bottom right. Therefore the bottom right corner also must be traversed in the same orientation as the bottom left corner. Applying this to other pairs of adjacent corners, we established our claim. We now color the board in a checkerboard manner (i.e. alternate black and white), and iterate through the edges of $G_3$. Since each node in $G_1$ and $G_2$ are 1-regular, the edges in $E_1$ and $E_2$, when iterated in that order, must come alternately from $G_1$ and $G_2$. Now according to our iterating direction, colour the edge according to the starting square of the edge. Since the four corners are traversed in the same orientation, the black edges that pass through each corner must also have the same direction (thereby all belonging to the same layer), so the conclusion follows. $\blacksquare$