The motivation for this article is to derive strict convexity of the surface tension for Lipschitz random surfaces, that is, for models of random Lipschitz functions from $\mathbb Z^d$ to $\mathbb Z$ or $\mathbb R$. An essential innovation is that random surface models with long- and infinite-range interactions are included in the analysis. More specifically, we cover at least: uniformly random graph homomorphisms from $\mathbb Z^d$ to a $k$-regular tree for any $k\geq 2$ and Lipschitz potentials which satisfy the FKG lattice condition. The latter includes perturbations of dimer- and six-vertex models and of Lipschitz simply attractive potentials introduced by Sheffield. The main result is that we prove strict convexity of the surface tension -- which implies uniqueness for the limiting macroscopic profile -- if the model of interest is monotone in the boundary conditions. This solves a conjecture of Menz and Tassy, and answers a question posed by Sheffield. Auxiliary to this, we prove several results which may be of independent interest, and which do not rely on the model being monotone. This includes existence and topological properties of the specific free energy, as well as a characterization of its minimizers. We also prove a general large deviations principle which describes both the macroscopic profile and the local statistics of the height functions. This work is inspired by, but independent of, Random Surfaces by Sheffield.