Just to clarify some terminology, a VPN (Virtual Private Network) is not the same thing as a VPS (Virtual Private Server). You're thinking VPS.
I don't want to get into specifics of hosting recommendations, as that could get messy (if hosts catch wind of this thread, every single one will be coming here to pitch you on their own offering).
It depends on how each host defines "installation." One host might consider one multisite network with a million subsites to be one installation. Another host might consider that same setup to be 1,000,001 sites.
It would be best to ask for clarification on hosts you're considering, because some managed WordPress hosts do adjust pricing for multisite.
It's also important to note that you don't need to keep all your eggs in one basket. It's totally fine to host your multisite network on one host, and your other sites on another. I wouldn't let this factor into your decision too much.
In any case, I always advocate for starting small and working your way up as needed. Many go all in with an expensive VPS or dedicated server, even though their site would've performed just fine on a much cheaper, shared host. Then complain about "wasting money" when it turns out their site wasn't as successful as they hoped.
I'd just pick any one of the options you mentioned, but keep a nice backup/migration solution at the ready in case you need to move. It's difficult to evaluate a host for your unique needs without actually trying it first. It's not worth getting into "analysis paralysis" over it.