Spitzmann,
Realmente o desempenho poderá ser afetado!!!
Eu não consegui entender a seguinte colocação "Um colega da empresa disse que mesmo os registros que estejam dentro do range de CEPS e com a cidade já definida, sofrerão update. Gostaria de fazer o update somente nos registros que não estejam com a cidade correta."
Se você deseja alterar somente uma faixa de valores determinados, isso representa que você esta limitando o seu result set, desta forma, o SQL Server deverá processar e atualizar somente os registros que são satisfatórios na condição determinada.