You don't need to make it less random to achieve that. A 100% random shuffle won't have that issue, you just have to make sure it's actually a shuffle and not something else.
Suppose shuffling results in ordered set [b, a, c]
Suppose user plays through the entire set. Now it's shuffled again before repating.
Suppose the new shuffle results in ordered set [c, a, b]
The user now hears c play after c
2. Your claim is not even true as written.
3. I'm tempted to assume the user has a reasonable amount of music, so it will last as long as necessary. And you can't force me not to assume that.