We study "random surfaces," which are random real (or integer) valued functions on Z^d. The laws are determined by convex, nearest neighbor, difference potentials that are invariant under translation by a full-rank sublattice L of Z^d; they include many discrete and continuous height models (e.g., domino tilings, square ice, the harmonic crystal, the Ginzburg-Landau grad-phi interface model, the linear solid-on-solid model) as special cases. A gradient phase is an L-ergodic gradient Gibbs measure with finite specific free energy. A gradient phase is smooth if it is the gradient of an ordinary Gibbs measure; otherwise it is rough. We prove a variational principle--characterizing gradient phases of a given slope as minimizers of the specific free energy--and an empirical measure large deviations principle (with a unique rate function minimizer) for random surfaces on mesh approximations of bounded domains. Using a geometric technique called "cluster swapping" (a variant of the Swendsen-Wang update for Fortuin-Kasteleyn clusters), we also prove that the surface tension is strictly convex and that if u is in the interior of the space of finite-surface tension slopes, then there exists a minimal energy gradient phase mu_u of slope u. This mu_u is always unique for real valued random surfaces. In the discrete models, mu_u is unique if at least one of the following holds: d is in {1, 2}, there exists a rough gradient phase of slope u, or u is irrational. When d=2, the slopes of all smooth phases (a.k.a. crystal facets) lie in the dual lattice of L.

177 pages, 10 figures