I never used to have this problem until recently, when it started happening every time I’d start my car - and even every time I’d stop playing other media in my car.

I ended up uninstalling Apple Music. At least they let you do that.