Regarding my own Problem: Renewing the cert with certbot and --preferred-chain="ISRG Root X1" did indeed help. After doing that my android happily accepts connections to my own DoT-Server again.
I've posted the same issue (and now solution) on reddit as well:
Regarding certbot - why is ubuntu's version using apt that ... old?
But im not sure which solution was indeed needed here:
- update certbot
- --preferred-chain="ISRG Root X1"