Вы можете установить несколько версий иконки в разных разрешениях, и Gnome должен выбрать лучшую в зависимости от контекста. Например, в Fedora 15 пакет firefox устанавливает несколько значков:
/usr/share/icons/hicolor/16x16/apps/firefox.png
/usr/share/icons/hicolor/22x22/apps/firefox.png
/usr/share/icons/hicolor/24x24/apps/firefox.png
/usr/share/icons/hicolor/32x32/apps/firefox.png
/usr/share/icons/hicolor/48x48/apps/firefox.png
/usr/share/icons/hicolor/256x256/apps/firefox.png
Вы даже можете установить масштабируемый значок, поэтому, если он захочет (в настоящее время это не так), пакет firefox может установить:
/usr/share/icons/hicolor/scalable/apps/firefox.svg
Затем в файле рабочего стола для приложения просто дайте название иконки, например:
Icon=firefox
и Gnome должен все уладить и выбрать лучший значок для каждого контекста, где он его использует.