In general scientific literature it is said that surface energy of solids is always positive but there is an unsaid assumption being made while doing so. The assumption being that we are talking about a pure single component system.
The more accurate way to say this would be,
The surface energy of all pure single component solids is positive.
Now coming to the question, "Can surface energy be negative?". The answer is yes!
This can happen as you pointed out, if molecules on interphase have lower potential energy compared to the bulk. Now, this lowering of potential energy might happen due to some chemical interactions at the interface, with some other component which is present in the system.
This has also been experienced in practice like in the article, Interface Stresses and Their Effects on the Elastic Moduli of Metallic Multilayers(1).
The appearance of negative interface stresses and negative interface
energies in Table II seems surprising at first sight. However, the
negative interface energy $\gamma_{111}$ for the Pt/Ni system can be understood
if we introduce the idea that the interface energy of a semicoherent
heterophase boundary contains a chemical component, which arises from
the chemical inhomogeneity in the interface region, and a structural
component due to the distortions associated with misfit dislocations.
(See Ref. 19 for details. ) The chemical component should be negative
for all chemically abrupt interfaces in miscible systems with negative
mutual heats of solution. ' If it is also larger in absolute value
than the structural component, a negative semicoherent interface
energy is obtained. Negative interface stresses may also appear on
boundaries with positive interface energy, because the sign of the
second term in Eq. (3) can be either positive or negative. Following
these arguments we expect a loose correlation of the interface
stresses and energies with the mutual heats of solution, which is
present in our results on the (100) boundary plane as well as on the
(ill) boundary plane, as seen in Table II
Reference:
(1) Gumbsch, P.; Daw, M. S. Interface Stresses and Their Effects on the Elastic Moduli of Metallic Multilayers. Phys. Rev. B Condens. Matter 1991, 44 (8), 3934–3938. https://doi.org/10.1103/physrevb.44.3934.