Eu acho que o SVG é o preferido, porque eles são dimensionáveis para qualquer tamanho. Isso também deve responder à sua segunda pergunta.
Para outros formatos, há vários tamanhos. Eu tenho as seguintes contagens da minha instalação do Ubuntu. Com base nisso, acredito que você deva incluir 8, 16, 22, 24, 32, 48 e 256.
17M /usr/share/icons/gnome/scalable
628K /usr/share/icons/gnome/512x512
8.5M /usr/share/icons/gnome/256x256
208K /usr/share/icons/gnome/128x128
20K /usr/share/icons/gnome/64x64
2.0M /usr/share/icons/gnome/48x48
2.1M /usr/share/icons/gnome/32x32
1.9M /usr/share/icons/gnome/24x24
1.9M /usr/share/icons/gnome/22x22
2.1M /usr/share/icons/gnome/16x16
32K /usr/share/icons/gnome/8x8
Eu também encontrei um questionar no Ask Ubuntu, onde eles dizem que gostam de ver 16, 32, 64 e 128.
E uma pergunta no StackOverflow, onde eles diga 48 é um bom tamanho e tem algumas informações sobre como incluí-las.
Edit: As diretrizes do Freedesktop.org são aqui , que discute terminologia, diretórios e como os ícones são pesquisados.