Dado seu exemplo com o logotipo do Google: o logotipo tem uma paleta de cores indexada. Se você reduzir as dimensões de uma imagem indexada no Photoshop, o Photoshop usará a mesma tabela de índice de cores para a imagem menor. Assim, a imagem resultante parece péssima.
Você deve converter a imagem original da cor indexada para RGB com pelo menos 8 bits (por R, G, B). Em seguida, redimensione a imagem, ela ficará bem. Finalmente, você terá que converter essa imagem RGB de volta para a cor indexada (se precisar).