O banco atual é SQL Server e estou construindo agora com PostgreSQL.

Mudar de banco não vai ter diferença nenhuma. Você tem que aplicar práticas inteligentes de otimização de querys e indices.

milhões de registros por empresa

Milhões de registros não é nenhum problema para bancos bem configurados.

O limite teórico do PostgreSQL por tabela é 1 bilhão de registros. É a partir desse numero que otimizar é mais custoso que dividir.

A única coisa que na minha opinião vai resolver o problema é um bom DBA.

PostgreSQL vs SQLServer

Os dois vão ter um desempenho péssimo para querys mal estruturadas e mal indexadas

Os dois vão ter um desempenho semelhante para querys bem estruturadas e indexadas.

A diferença aqui só vai começar aparecer no bilhão.