Alkanes longer than n = 6 carbons do not spread on the water surface, but condense in a macroscopic lens. However, adding trimethylammonium-based surfactants, C,TAB, in submillimolar concentrations causes the alkanes to spread and form a single Langmuir-Gibbs (LG) monolayer of mixed alkanes and surfactant tails, which coexists with the alkane lenses. Upon cooling, this LG film surface-freezes at a temperature T-s above the bulk freezing temperature T-b. The thermodynamics of surface freezing (SF) of these LG films is studied by surface tension measurements for a range of alkanes (n = 12-21) and surfactant alkyl lengths (m = 14, 16, 18), at several concentrations c. The surface freezing range T-s-T-b observed is up to 25 degrees C, an order of magnitude larger than the temperature range of SF monolayers on the surface of pure alkane melts. The measured (n,T) surface phase diagram is accounted for well by a model based on mixtures' theory, which includes an interchange energy term omega. omega is found to be negative, implying attraction between unlike species, rather than the repulsion found for SF of binary alkane mixtures. Thus, the surfactant/alkane mixing is a necessary condition for the occurrence of SF in these LG films. The X-ray derived structure of the films is presented in an accompanying paper.