We observe interlaced square vortex lattices in rotating two-component dilute-gas Bose-Einstein condensates (BEC). After preparing a hexagonal vortex lattice in a single-component BEC in an internal state $|1>$ of $^{87}$Rb atoms, we coherently transfer a fraction of the superfluid to a different internal state $|2>$. The subsequent evolution of this pseudo-spin-1/2 superfluid towards a state of offset square lattices involves an intriguing interplay of phase-separation and -mixing dynamics, both macroscopically and on the length scale of the vortex cores, and a stage of vortex turbulence. Stability of the square lattice structure is confirmed via the application of shear perturbations, after which the structure relaxes back to the square configuration. We use an interference technique to show the spatial offset between the two vortex lattices. Vortex cores in either component are filled by fluid of the other component, such that the spin-1/2 order parameter forms a Skyrmion lattice.