We report the experimental observation of a square crystalline phase in a vibrated binary mixture of spherical grains. This structure spontaneously forms from a disordered state, consistently with predictions obtained in an equilibrium system with similar geometrical properties under conservative dynamics. By varying the area fraction, we also observe stable coexistence between a granular fluid and an isolated square crystal. Using realistic simulations based on the discrete element method and an idealized collisional model integrated via event-driven molecular dynamics, we not only reproduce experimental results but also help to gain further insights into the non-equilibrium phase coexistence. Through the direct phase coexistence method, we demonstrate that the system shows behavior highly similar to an equilibrium first-order phase transition. However, the crystal remains at a higher granular temperature than the fluid, which is a striking non-equilibrium effect. Through qualitative argument and supported by kinetic theory, we elucidate the role of the coupling between local structure and energy transfer mechanisms in sustaining kinetic temperature gradients across the fluid-solid interface.