What would be the minimum spec for the maximum increase in performance for such a server?
I'm running it on a Hetzner CPX31 VPS with tops 30 people using NC Talk simultaneously and I think I've never seen it go beyond 70% CPU usage. Honestly I could probably scale it down to a CPX21.
What are the features that we would want to find, so that we can be cost effective?
Any VPS should do, really. It's nothing fancy, just a SFU/Turn server.
If we run several nextclouds, could we setup on HPB and then use it for all the different nextclouds?
Yes, I'm using it on four different NC instances simultaneously no problems.
GNU/Linux Debian based or is GNU/Linux Debian a requirement? For example, would an Ubuntu VPS do as well?
Debian is a requirement for this installation. But you can simply use a different install method and Ubuntu should work too.