I’ve had the same problem. Started a couple months ago just like you said.
It looked like a few of my songs were corrupted, so I deleted them. It didn’t work.
I’ve deleted the library and re-created multiple times. I’ve also deleted the Plex server database and let it create a new one. Still didn’t work.
It was a date problem on two albums. (release date)
Check the album that first is playing, remove the date and write it again and save. Is it more album that is always first just update the release date.