Same here. Until December the Spotify shuffle functioned reliably on Google Home devices, but there are now also problems. It seems that Amazon and Google don't want the shuffle to work on Spotify. It works for Amazon Music and Google Music.
Since Spotify does not respond to user complaints I don't see any reason why I shouldn't change to another music provider.