I use the official jellyfin client on my phone. I hear you in that I have also wanted some randomness in selecting what to listen to.
I keep the standard Album category and use the random sort. Then I still get some agency in selection, but it's all mixed.
Edit: Confirmed minimum is Android 5.0 or newer.