> What would be a good way to get started?

Rent a Linux server, deploy the Tailscale client, run apps on it.

> should I really self-host on shared CPUs

That shouldn't generally be a problem unless you're a very high value target (or really unlucky), but if you're that worried, rent a bare metal server.