I see some streamers taking song requests and they pretty much always have the song that was requested, did they go and individually download every song or am I missing something here? (No they were not official dlc songs)

They do download individual song but most of the request are usually the same again and again so after 1 or 2 month of streaming you won't have to download many more song on request and you just need to get the new released CDLC which isn't that much.