When I bought a 40gb music player in 2005, I stopped downloading songs and started downloading discographies of entire artists and labels. The change that came with streaming services wasn't the first one.
I'd download entire music libraries (from Soulseek where you can browse people's shared files). I'd look up something I liked and assume someone who likes it has good taste :) And download whatever else seemed interesting. Thus my iPod became a vehicle for discovering new music.