I agree with your observations. The shuffle function is not very good on the Fuze. I use it a lot, and find that it seems to find artists that it keeps going to back to for that session. I shuffle by genre mostly, and may have 1200 songs in a genre. But it will repeatly go back to the same general area of the list and hit the same artists over and over.
And yes, it does seem to hit certain songs way more than others. My wife complains about this when I shuffle through her music that I have on the player. There are songs you seem guarenteed to hear every single time, and others that don’t seem to come up, no matter how long you listen. I would love to know what the algorithm is that it uses.
One question though. If you hate the songs, why are they on your player?