VPS or Virtual Private Server. It's a computer or server you rent from a big company like DigitalOcean for an amount of money monthly (or yearly or hourly even) so you can host your own website or self-host 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 the best privacy, You might look for self-host 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 depends on your use case and money you have. Most of the big companies will not risk their reputation to get into your little VPS, so do not worry about that. But you can set up 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 to 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)
After you buy your VPS from your favorite provider, and choosing the distro (I will assume it's Debian), make sure you have sudo or root rights and make sure your distro is up-to-date (The following command will vary from distro to another, again I will assume your server distro is Debian):
sudo apt update && sudo apt upgrade