This is an optimization job, and a pretty complex one if you are looking for the optimal solution. Fortunately I believe it to be one of those cases where good enough will do.
First thing to do is to establish a mathematical quality criterion, that is a formula that given a permutation of the list will return a single number describing how good or bad that permutation is.
A simple formula suggestion, each criteria that you would like taken into account should be given a weight, give a high weight to important criteria, and a low weight to criteria where a lot of songs share the same property, so that those do not dominate:
For each song on the list
For each other song on the list
For each criteria
If the two songs share that criteria
Add to the quality value: square root( [criteria weight]/[distance between the two songs] )
The lower a value this procedure produce, the better the list permutation is.
Making the permutation
Now you could take this formula to math.stackexchange and have them tell you how insanely difficult and possibly practically impossible it is to find the optimum solution for anything but a trivial number of songs, or you could just throw clock cycles at it and get a good solution.
There are many ways of doing this, here is one:
Start with a random permutation of the list.
Several million times do the following:
Select two entries at random
For each of those two entries calculate their contribution to the quality value
Swap the positions of the two entries
Calculate the contribution to the quality value of the two entries at their new position
If the sum of the calculations in the new positions is greater than the sum in the old positions
Swap back
This is a somewhat wasteful algorithm, but it is easy to implement and can deal with as many criteria as one desire.
Optimizations
Loads of different tweaks and optimizations can be applied, here are a few:
In quality value calculation, don't bother checking a song against every other song on the list, instead just check it against the 100 or so closest songs. For common values this speed optimization has practically no influence on the quality of the result.
For a rare value of a given property it may be more efficient to track the existing instances of that value than to search for them.
If you feel that it is important that values that have few instances get spaced close to even, rather than just far apart it is probably necessary to increase the weight for those specific values, but not for other values of that criterion.
A pseudo-random function that pick all possible pairs from the list in equal distribution may have a slightly better efficiency per pick than a normal random pick.
while (length(songs) > 0) { x := rand(); addElem(shuffle, songs[x]); remElem(songs, x); }
, but you say you want an "ultimate shuffle". I don't know what you really want with that, even reading the question...