We investigate the 1/3 monolayer $alpha$-Pb/Si(111) surface by scanning tunneling spectroscopy (STS) and fully relativistic first-principles calculations. We study both the high-temperature $sqrt{3}timessqrt{3}$ and low-temperature $3times 3$ reconstructions and show that, in both phases, the spin-orbit interaction leads to an energy splitting as large as $25%$ of the valence-band bandwidth. Relativistic effects, electronic correlations and Pb-substrate interaction cooperate to stabilize a correlated low-temperature paramagnetic phase with well-developed lower and upper Hubbard bands coexisting with $3times3$ periodicity. By comparing the Fourier transform of STS conductance maps at the Fermi level with calculated quasiparticle interference from non-magnetic impurities, we demonstrate the occurrence of two large hexagonal Fermi sheets with in-plane spin polarizations and opposite helicities.