This paper proposes a complex fast recursive least-squares (FRLS) channel-estimation algorithm for single-carrier electromagnetic (EM) communications across the seawater–air interface, where severe attenuation and multipath cause strong SNR fluctuations. By redesigning the input-data structure and using forward–backward joint estimation, FRLS reduces the per-iteration complexity from the quadratic cost of classical RLS to a linear form (14L + 20 operations per iteration, where L is the channel length). Simulations under representative one- to three-path channels show that FRLS achieves the lowest steady-state mean-square deviation (MSD) at low SNR, outperforming LMS, IPNLMS, RLS, and PRLS. Offshore experiments further validate the practicality: after MMSE equalization, FRLS yields higher OSNR and improves the BER distribution, demonstrating an effective accuracy–complexity trade-off for hardware-constrained cross-medium EM links.