I personally prefer the iPod Nano 7th gen, which is great in terms of usability, has bluetooth 4.0 and is also very small size. Repair is a nightmare though and finding an affordable but still working device is not that easy.
If smallest size is not a requirement, you could go for the HiBy M300 - a pretty new Android 13 device supporting most Apps, 2TB of microSD Storage, having control buttons and also cable headphone remote support (OMTP, not CTIA), but still not that big.
Maybe a modified Apple iPod Classic 2009 with an iFlash Quad and 2000mah battery also fits your needs. It's way bigger than a shuffle, but it's at least maintainable (battery and storage replacement).
Apple did a really great job on remote controlling the devices with "tap"-Codes (tap, double tap, triple tap). The iPod Classic 2009 for example does not support the codes for fast forward / rewind (tap+tap_hold=ff, tap,tap,tap_hold=r). That's something I regularly use for audiobooks, so I'm tied to the iPod Nano 7g (the 6g would also work, but I prefer the larger display for navigating chapters).
There are android devices supporting these tap codes partially, but not as good / reliable as the iPod Nano 7g. Android also is using OMTP while Apple is using CTIA, so Apple headphones won't work on android and vice versa. CTIA=>OMTP Adapters (from amazon) just switch the pinout, which does not work, because Apple uses different Resistance on the Pinout.
I also "modded" one of my iPod Nano 7g by partially milling out the aluminium backplate and soldering in an iPod Mini battery (600mah), so that I got nearly 3 times the battery life of a factory iPod Nano as well as an easy to replace battery without opening the device (which is way to hard). The bigger iPod Mini battery does not fit without a silicone bumper, but since I already used one, it was perfectly fine. Changing the battery still requires soldering, but at least not fiddling with the very fragile display removal procedure.
However, currently I did not find a better device for my use case than the iPod Nano 7g. And everything is better with bluetooth... although I don't use it :-)
Older Androids used OMTP but they eventually standardised on CTIA too:
https://source.android.com/docs/core/interaction/accessories...
https://www.dhgate.com/product/m13-bluetooth-mp3-player-mini...
I can easily see myself buying one of those, adding a 512Gb uSD card on it and ditch Spotify.