Olha, redimensionando tudo, só o Cubic se apresentou bem ruim. Todas as outras são aceitáveis para exibição WEB. Umas melhores que outras. Cada algoritimo tem uma indicação própria. Alguns são mais generalistas, servem para várias situações diferentes. Os melhores, pelo que vi aqui, são o Lanczos e o Mitchell. O Bicubic (nome de arquivo bicbica) não gerou nenhum problema no resize.
ACHO, que o problema deve ser no site de hospedagem.
Cada imagem nomeei com o nome do algoritimo usado no resize. Dêem uma boa olhada antes de ver os nomes e tirem suas próprias conclusões:
PS: Usei o Mogrify para o resize. Ele tem 13 opções distintas de algoritimo. Não testei todos, apenas os 2 que mais uso e mais alguns aleatoriamente. O bicubic testei via PS. As imagens hospedei no imageshack sem interferência do site em redimensionar. Já li relatos de interferência do Imageshack na qualidade das imagens.