If I want to have artist Q mixed in, I'd have to enque or append and then re-shuffle (which admittedly gives you the songs you've already heard again).

Does it? If so, that's a bug. Unshuffling and reshuffling in that situation is meant to do exactly what you're looking for: leave you part-way through the playlist with, coming up, all the Q songs and exactly those X, Y and Z songs you haven't heard yet -- all shuffled together.

Peter