Can it really work if the server doesn't have a public IP? It works if the server blocks all incoming traffic, but doesn't it have to be routable? It can of course work via DHCP, but I would consider my devices at home still to have a public IP, even if they share it.
As I wrote, I'd consider being behind a NAT still having a public IP. It's a shared one but any web page will be able to see a public IP associated with this machine. That's different from servers that have no public IP and must route all traffic through a proxy.
If you consider devices behind a NAT to have a public IP than yes it needs a public IP. Really, it needs to just be routable to the internet. Tailscale handles the NAT busting and p2p handshake, while the nodes directly talk to each other (over WireGuard)
