We report the observation of the homogenous nucleation of crystals in a dense layer of steel spheres confined between two horizontal plates vibrated vertically. Above a critical vibration amplitude, two-layer crystals with square symmetry were found to coexist in steady state with a surrounding granular liquid. By analogy to equilibrium hard sphere systems, the phase behavior can be explained through entropy maximization. However, dramatic non-equilibrium effects are present, including a significant difference in the granular temperatures of the two phases.