I think this will end up being a "your mileage may vary" topic, but I don't get this behavior at all. Shuffle is very random and I don't get many repeat artists. If I do, I assume it's a random occurrence.

Over in the Wish List forum there was talk about having the shuffle explicity separate same-artist songs from a shuffle, but at this point it's just a wish list item.