In this paper we study the double layer interaction between two heterogeneous surfaces of either constant charge or constant potential. The surface heterogeneities are assumed to be distributed on periodic lattices of arbitrary structure. General expressions for the 3-D electrostatic potential distribution and the interaction free energy between the two surfaces are given. Asymptotic forms and numerical examples for the interaction potential are provided for the symmetric lattice problem. In general, the interaction potential or osmotic pressure decays exponentially at large separations. When a nonuniform, but net neutral, surface interacts with a uniform surface (charged or uncharged), the interaction can be either attractive or repulsive depending on whether the surfaces are constant potential or constant charge. For two nonuniform net neutral surfaces, the interaction can be either attractive or repulsive depending on whether the surfaces are constrained in configurations in which regions of unlike or like charge are in opposition. For this case, a statistical mechanical average over all relative lateral displacements shows that asymptotically the interaction will always be attractive. The magnitude of the attraction is comparable to or can exceed the van der Waals interaction. The results given here would warrant inclusion in any interpretation of surface force measurements in systems involving adsorbing, neutralizing surfactants.