Over the past thirty years, it has been consistently observed that surface engineering of colloidal nanocrystals (NC) is key to their performance parameters. In the case of lead chalcogenide NCs, for example, replacing thiols with halide anion surface termination has been shown to increase power conversion efficiency in NC-based solar cells. To gain insight into the origins of these improvements, we perform ab initio molecular dynamics (AIMD) on experimentally-relevant sized lead sulfide (PbS) NCs constructed with thiol or Cl, Br, and I anion surfaces. The surface of both the thiol- and halide-terminated NCs exhibit low and high-energy phonon modes with large thermal displacements not present in bulk PbS; however, halide anion surface termination reduces the overlap of the electronic wavefunctions with these vibration modes. These findings suggest that electron-phonon interactions will be reduced in the halide terminated NCs, a conclusion that is supported by analyzing the time-dependent evolution of the electronic energies and wavefunctions extracted from the AIMD. This work explains why electron-phonon interactions are crucial to charge carrier dynamics in NCs and how surface engineering can be applied to systematically control their electronic and phononic properties. Furthermore, we propose that the computationally efficient approach of gauging electron-phonon interaction implemented here can be used to guide the design of application-specific surface terminations for arbitrary nanomaterials.