So apparently removing the DISTINCT cuts the query time in half, but it's still very slow...
With DISTINCT: https://explain.depesz.com/s/cOeV
Without DISTINCT: https://explain.depesz.com/s/QAIM5
Aha, forgot that UNION also does a uniqueness check. Changing it to UNION ALL fixed that.