Su Ubuntu:
fai clic con il pulsante destro del mouse sull'icona che non ti piace -> Proprietà -> nella finestra aperta fai clic sull'icona -> scegli un'icona che desideri
Gli eseguibili su Linux non hanno icone incorporate (prova a puntare il tuo file manager su /usr/bin ). Quello che hai visto è probabilmente un Desktop Entry. Questo è un file di testo che descrive l'icona, il nome del programma e l'eseguibile.