We investigate electron-phonon coupling in the molecular crystals CH$4$, NH$3$, H$2$O, and HF, using first-principles quantum mechanical calculations. We find vibrational corrections to the electronic band gaps at zero temperature of -1.97 eV, -1.01 eV, -1.52 eV, and -1.62 eV, respectively, which are comparable in magnitude to those from electron-electron correlation effects. Microscopically, the strong electron-phonon coupling arises in roughly equal measure from the almost dispersionless high-frequency molecular modes and from the lower frequency lattice modes. We also highlight the limitations of the widely used Allen-Heine-Cardona theory, which gives significant discrepancies compared to our more accurate treatment.