How does endless amount of listener history and preference data give them the upper hand? That data wouldn't exist if they weren't able to license content.

Google and Apple have that too -- YouTube and iTunes have been around longer than Spotify, and likely have similar data sets.