I would like to know if it's possible to have multiple companies running in a single instance of NopCommerce, or I will have to install a new instance for each client that wants an eCommerce solution.
It depends on your requirements. If you have once store and one product database, but want to run it for multiple countries and currencies then you can use nopCommerce multiple store support.
If you clients are different companies and they have different product databases then I'd recommend to have nopCommerce installation per client.
As above, all depends on your/companies requirements.
nopCommerce as single platform to sell by number of companies is ready to use - see vendor feature. But vendor account has some limitation. Not sure, if companies would like to have this limitation.
The best way it would be to create test environment and made some tests. Then show results to companies and you will know which way would be the best. Please note, some vendor limitation may be extended by plugins.