Today I installed Tesla software version 2024.20.1 and I noticed that Bluetooth audio processing has much less delay now, playing and skipping songs almost instantly. That was certainly not the case before, taking about a second to notice the action (playing, pausing, skipping, etc.) in any app.
The Plex apps also play fine now and I do not see any mixer underflowed warnings in the debug logs anymore.
The delay problem was definitely in the Tesla software, but I also think that other apps could handle the delay better than the Plex apps. There is room for improvement there, but I understand that the urgency depends on how many similar cases of delay in bluetooth audio processing people experience daily (very likely not many :))
Keeping my fingers crossed, and so far I think we can safely say that the problem is solved for me.