The observation of replica bands in single-unit-cell FeSe on SrTiO3 (STO)(001) by angle-resolved photoemission spectroscopy (ARPES) has led to the conjecture that the coupling between FeSe electrons and the STO phonons are responsible for the enhancement of Tc over other FeSe-based superconductors. However the recent observation of a similar superconducting gap in single-unit-cell FeSe/STO(110) raised the question of whether a similar mechanism applies. Here we report the ARPES study of the electronic structure of FeSe/STO(110). Similar to the results in FeSe/STO(001), clear replica bands are observed. We also present a comparative study of STO(001) and STO(110) bare surfaces, and observe similar replica bands separated by approximately the same energy, indicating this coupling is a generic feature of the STO surfaces and interfaces. Our findings suggest that the large superconducting gaps observed in FeSe films grown on different STO surface terminations are likely enhanced by a common mechanism.