The phase behavior and surface pattern formation for intermediate size Lennard-Jones clusters on rigid surfaces are examined. We use a parallel tempering Monte Carlo algorithm, in the canonical ensemble. Tempering is done over the temperature domain in most of the calculations. A two-dimensional temperature and Hamiltonian tempering algorithm is also implemented, to examine its usefulness in investigating this type of problem. In general, we observe gas phase systems as they undergo a condensation transition on the surface, followed by a freezing transition. The final solid state pattern formed by the cluster on the surface is the result of a number of competing effects. First, there is a competition between attraction within the cluster and that between cluster and surface atoms. Second, a monolayer of Lennard-Jones atoms tends to pack in a hexadic geometry. This geometry is frustrated on a surface with a different symmetry. The molecular organization of the substrate has a serious impact on the cluster packing. The surface morphology and the size mismatch between cluster and surface atoms, along with the relative interaction strengths, determine which of the effects prevail. When the surface atoms are small enough, the interactions within the cluster determine the symmetry of the pattern. In such a case, the substrate behaves similarly to a continuous surface, and the low-temperature pattern is a hexadic monolayer. When the sizes of the surface and cluster atoms are comparable, the low-temperature adsorbed geometry mimics the substrate symmetry. On a face-centered cubic surface, face-centered cubic monolayers or droplets are obtained.