Não sei se isso vai te ajudar, mas se reparar na pasta /usr/share/icons, vai ver que cada pasta de ícones tem subpastas com tamanhos para eles, tipo 16x16, 22x22, 48x48... de repente tu pode ir testando esse ícones no teu desktop, buscando uma padronização para o tamanho deles. Mas é como o andretyn disse, no final depende muito do tamanho da imagem que o programa em questão atribui ao ícone, alguns não tem a mesma variedade de tamanhos que outros tem, especialmente programas que não são nativos do Ubuntu.