How to get a VPS
VPS or Virtual Private Server. It's a computer or server you rent from big company like digitalocean for amount of money monthly (or yearly or hourly even) so you can host your own website or selfhost some open source projects like invidious for example. You really can't fully trust them as in the end it's someone else's computer and if you really want to achieve best privacy, You might look for selfhost at home.
Privacy and security depend on company also your use case depend on company too. There are some well known players like digital ocean, Vultr and Hetnzer (I use the latter). Again it depend on your use case and money you have. Most of big companies will not risk their reputation to get into your little VPS so do not worry about that. But you can setup an encrypted partition with luks maybe but again it's not bulletproof so you have to trust the company you rent from.
So to choose a VPS first select a budget and your use case, for example some VPSes does not allow hosting tor exit nodes or does not open port 25 (smtp port for emails) by default to prevent spam. So it's really about your use case and yup! make a list and then go up on reddit r/selfhosted and say I want VPS that allow me to do this and that and i'm sure you will find someone help you :) or try to search online and try your luck
My recommendation though right now I use both Hetnzer and Kimsufi and both are great. Also a tip about hetnzer that there is a coupon code valid for 3 months so do not forget to use it :) (you might contact their support to get it as they love to hide it)