Interesting write up! Did you happen to try this with a CTE instead of a subquery? ie something like:

  WITH
    tmp AS (SELECT accounts_other.id, COUNT(*) n
              FROM accounts accounts_other
              JOIN stacks stacks_other ON accounts_other.id = stacks_other.account_id
              JOIN runs runs_other ON stacks_other.id = runs_other.stack_id
             WHERE (stacks_other.worker_pool_id IS NULL OR
                    stacks_other.worker_pool_id = worker_pools.id)
               AND runs_other.worker_id IS NOT NULL
             GROUP BY 1
            )
  SELECT COUNT(*)                                                                  as "count",
         COALESCE(MAX(EXTRACT(EPOCH FROM age(now(), runs.created_at)))::bigint, 0) AS "max_age"
  FROM runs
    JOIN stacks ON runs.stack_id = stacks.id
    JOIN worker_pools ON worker_pools.id = stacks.worker_pool_id
    JOIN accounts ON stacks.account_id = accounts.id
    LEFT JOIN tmp ON tmp.id = accounts.id
  WHERE worker_pools.is_public = true
    AND runs.type IN (1, 4)
    AND runs.state = 1
    AND runs.worker_id IS NULL
    AND accounts.max_public_parallelism / 2 > COALESCE(tmp.n, 0)

I don't know this for sure, but in my experience it has seemed like Postgres is bad at optimizing subqueries, and will execute once per row.