evenly distributing duplicates throughout a randomized list (playlist shuffle)

I need to shuffle about 1,000 strings of the form "title - artist", where a number of the titles repeat (say "Silent Night"), and a number of the artists repeat (say, "Bing Crosby"). None of the "title - artist" combos repeat, and there are no additional hyphens.

I'd like to end up with a list with as much space as possible between identical titles and between identical artists.

I'm leaning toward just randomly shuffling the whole list many thousands of times, and keeping whichever one has the greatest distance between the closest pair of identical repeats.

Another brute force: shuffle (just once) then repeat tons of times: find the closest pair and swap one of them into a different random spot.

One seem better than the other? Anything a little smarter, but still easy?

Thanks a ton!