We study the electronic structure of the Pd-terminated surface of the non-magnetic delafossite oxide metal PdCoO$_2$. Combining angle-resolved photoemission spectroscopy and density-functional theory, we show how an electronic reconstruction driven by surface polarity mediates a Stoner-like magnetic instability towards itinerant surface ferromagnetism. Our results reveal how this leads to a rich multi-band surface electronic structure, and provide spectroscopic evidence for an intriguing sample-dependent coupling of the surface electrons to a bosonic mode which we attribute to electron-magnon interactions. Moreover, we find similar surface state dispersions in PdCrO$_2$, suggesting surface ferromagnetism persists in this sister compound despite its bulk antiferromagnetic order.