Как рассчитать статистически значимый размер выборки на основе общего количества записей? (Postgres)

Вы можете использовать оконные функции:

select t.*
from (select t.*,
             row_number() over (partition by department order by rand()) as seqnum,
             count(*) over (partition by department) as cnt
      from t
     ) t
where seqnum < <your formula based on department size here>;

Я не знаю, какая у вас формула для статистической значимости, но вы можете подключить ее, используя размер отдела (cnt), вычисленный в подзапросе.