They negotiate with very few artists and their managers directly. The reason is that there are very few artists who have that kind of control of their content.

AC/DC, Led Zeppelin, the Beatles and Taylor Swift come to mind, but there are very few artists who have a say in whether or not their catalog can or can not be streamed. Those artists made wise business decisions at some point and/or were able to throw their weight around. Here are some notable hold outs as of 2016 anyway:

https://consequenceofsound.net/2016/02/which-artists-are-sti...

Using Pink Floyd as an example, the decision was there's and not their record label EMI:

http://www.rollingstone.com/music/news/pink-floyd-catalog-ar...

You should really count the Premium (paying) users only. The others don't make the company any money.

The per-user costs here are web servers and customer support. The bulk of the servers are only doing one thing, so even though there are a lot of them, you could mange them with a hundred people. So that leaves customer service as a per-user cost. It's possible that the customer support department has 2000+ people, and that would be a satisfactory answer. But if that's not the case, then "employees per user" is pretty irrelevant, and the question stands.