I've been dealing with this issue for a few months, just like everyone else on this thread. It's clearly a bandwidth issue unrelated to the individual streaming provider, because slacker and tunein are affected exactly the same way. Try loading a long podcast on tunein - the light grey bar takes minutes to move even slightly, whereas on Wifi the entire thing loads in a minute or two. When playing on slacker you can see that the song buffering just barely stays ahead of playback. And those times when the music does catch up the player, instead of pausing, gets a buffer underflow and loses its mind for a while (likely a separate quality issue with the media player).
I just brought in my car for service and got a somewhat older loaner. I gave the media player a try, and was delighted to see that songs were loading just fine while driving the same routes I drive every day. The grey buffering bar zipped right along, just like mine used to do, and playback was flawless. "Aha", I thought, "there must be a new FW update to fix the problem", but I checked the FW version and it was older than mine. Then I looked at the cell icon - it said "3G". This car doesn't have LTE, and it doesn't have the problem.
So the common link is LTE. Would AT&T choose to only throttle Tesla LTE and not 3G? That seems somewhat unlikely. It seems to me that the problem is on the Tesla end. Either they broke LTE somewhere, or Tesla is doing the throttling themselves.