Adicionar a mesma fórmula na coluna C em vez de (/ adicionalmente) formatação condicional deve ter o melhor desempenho. Se isso ainda não estiver bom, considere converter essas fórmulas em valores estáticos (é claro que você precisará atualizá-las manualmente, mas dessa forma você pode adicionar formatação condicional na coluna C). Tem certeza de que precisa manter as colunas A e B próximas umas das outras? Se você pudesse mover a coluna B para uma folha diferente e classificá-la seria mais rápida. Outras opções seriam o VBA, mas certamente é mais lento do que usar fórmulas integradas.