I also tried a lot of solutions, many of which were listed in this post, but none of them worked. Finally the answer as a comment to this question helped out - with or without the other solutions - the 2.4 GHz Wi-Fi was causing the problem.
Turning it off and listening to music from spotify offline was no longer choppy, using a 5 GHz Wi-Fi hotspot was OK, so now I've switched to a wired connection. I was going to be upgrading my router to a 5 GHz one anyway...
A possible explanation might be that the bluetooth and Wifi share the same antenna. The bug that seems to be causing this - link. It is explained there that a fix for it would be released in pulseaudio 12. The version that ships with ubuntu 18.04 is Version: 1:11.1-1ubuntu7.11
.
I tried manually upgrading that to version 12 (per this post) and I succeeded (Version: 1:12.2-9~bionic1
), but that did not stop the stuttering for me.
P.S. Using an HP Probook 440 G7, Ubuntu 18.04