Time- and frequency-domain 3-wave mixing spectroscopies (infrared + visible Sum Frequency Generation, SFG) are presented as the lowest-order nonlinear techniques that are both surface-selective and capable of measuring vibrational coherences. Application to ordered Langmuir-Blodgett monolayers shows vibrational quantum beats in time domain, which are connected to the frequency-domain spectrum by a simple Bloch-type model. The beat pattern is shown to be sensitive to the molecular order in the film. A mixed time-frequency domain version of this technique is applied to study ultrafast dynamics of the hydrogen bond network of interfacial water. Along with the vibrational dephasing, we observe ultrafast spectral diffusion of the OD stretch of D2O at the CaF2 surface, indicating rearrangement of the H-bond structures on the 50-100 fs time scale.