I considered crowdsourcing, but opted for a device over solving the “cold-start” problem as I thought I’d get more complete data (and have more success)
Not quite my take. My phone (Pixel) listens for music even when locked. Since I opted in it keeps log too. It fascinates me to see what music I accidentally heard during the day. That's Google doing it, so I guess my idea was probably only for them to do, matching music and location by default.
The rest of the problem is left for the reader to solve ;)