We examine several variational methods for determining bounds on the free energy of model crystalline phases, as applied to hard spheres in one and three dimensions. Cell- and harmonic-based reference systems are considered. Methods that provide the tightest bounds on the free energy are similar in form to free-energy perturbation, and are prone to inaccuracy from inadequate sampling. Gibbs-Bogoliubov formulas are reliable but weaker. For hard potentials they can give only a lower bound, indicating that their ability to provide upper bounds for other potentials is limited. Nevertheless, bounds given by Gibbs-Bogoliubov when applied with the optimal harmonic system prescribed by Morris and Ho [Phys. Rev. Lett. 74, 940 (1995)] yields impressive results; for hard spheres at higher density it is, within confidence limits, equal to the exact hard-sphere free energy.