I actually just had this problem a couple weeks back. I was using revanced spotify but I had to keep re-patching it because it kept breaking. Eventually, I became so frustrated I said fuck spotify and found ViTune which is a fork of ViMusic (which is now defunct).

It workes exactly how I would want a music app to work. No accounts, no algorithms, just search for the song you want. You might get a playback error if you're using a VPN, but that's literally the only complaint I have about it.