We study the low-energy surface electronic structure of the transition-metal dichalcogenide superconductor PdTe$_2$ by spin- and angle-resolved photoemission, scanning tunneling microscopy, and density-functional theory-based supercell calculations. Comparing PdTe$_2$ with its sister compound PtSe$_2$, we demonstrate how enhanced inter-layer hopping in the Te-based material drives a band inversion within the anti-bonding p-orbital manifold well above the Fermi level. We show how this mediates spin-polarised topological surface states which form rich multi-valley Fermi surfaces with complex spin textures. Scanning tunneling spectroscopy reveals type-II superconductivity at the surface, and moreover shows no evidence for an unconventional component of its superconducting order parameter, despite the presence of topological surface states.