Is it easy/cheap to get a stable IP address? I would worry that if I just get any cheap VPS host, they might switch the IP address at any point, but I'm not sure how true that actually is.
Easy yes. Even VPS providers need to maintain the IP, since your DNS typically points to that IP. You can also typically move the IP to another machine from the same provider.
But as a resut, VPS often have a different price for public IPs compared to private IPs. For instance, it costs €0.004/h per IP at Scaleway.
I've used dozens of VPS providers in the past, albeit 'low end' in this instance- they constantly change IP addresses because they're renting them, buying them, etc.
For IPv4 definitely a problem.
I maybe used around 100 VPS hosts, less well known ones beyong DO etc. I'd get a dozen IP change notices a year.