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.
I'm going to ignore the other ways to handle that and just point out that that is multiple shuffles and won't be a problem if the user initiates all shuffles.
If the user has to initiate all shuffles, it won't play continuously. If you handle it another way, that demonstrates that it doesn't "just" work with a pure shuffle without using those tricks.
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