Pretty sure iPod Classic did this.

But now I imagine most people don't mind looking at the app every 30-90 minutes to choose a new album.

Also just looking at my saved albums in Spotify there's loads of crap in there just because I've downloaded it offline once in the past 10 odd years. A shuffle of these albums would suck.

So they'd probably have to fix the saving/favouring of albums before allowing shuffling of them.