Suggestion:

simple 'random' play modes tend to not work well in practice.
(No offense to Kagu: it's the result of mathematically desirable random distributions.)

Long story short: in any decently-sized playlist you'll almost certainly hear some songs several times before you hear every song at least once. (again, something you want from a RNG, just not something you want when listening to music )

The accepted workaround in other apps (e.g. Winamp) is that they randomize the playlist, ensuring a good scramble but without the undesirable parts.

Since Kagu is still in the middle of adding advanced playlist support, had you considered a simple feature where Kagu creates a 'scrambled' play order in memory?

E.g.

I load Kagu, select All Songs, click the Add All button - it creates the familiar playlist of x-hundred songs, but also maintains an additional 'random play sequence' field for each track. Kagu populates this field by randomly choosing a play 'slot' from an array of as-yet-unassigned slots based on the total length of the playlist.

Then, when I select 'random' as the play-order, it doesn't jump to the next song based on random movement through the playlist, it simply moves to the 'next' song according to this random play order field.

Alternately: You could create a random play order list when Kagu opens, from some arbitrarily large 'list' (say, 5000 songs). And then when someone is in random mode, you choose the next song by referring to said pre-generated list.

If their actual playlist is smaller than the arbitrarily large list, you simply 'wrap around'.
E.g. if 523 comes up as 'next' in a list of 300, just play track 223.