Eu deixo Gnome-Do fazer o trabalho para mim.
O Gnome-Do se adapta para preferir seus aplicativos mais usados, então eu uso Super + Espaço para iniciar o Gnome-Do, e então r para iniciar o Terminal.
O benefício que recebo é que qualquer letra no comando corresponderá, desde que eu a insira em sequência. ou seja, eu tenho o Google Ch Roma e Ch romi u m Navegador Web, digitando Ch seleciona o primeiro, e Chu seleciona o último.
O segundo benefício é que ele deixa um monte de combinações de teclas para usar no controle das janelas e espaços de trabalho.
O benefício real do Gnome-Do é que esta solução se adapta bem : abro quase todos os meus aplicativos usados com frequência (eu estimaria em torno de 20 a 25 deles), usando 2 pressionamentos de tecla em média além de Super + Espaço .
Caso você esteja se perguntando sobre o uso do r para o Terminal, é porque t corresponde ao Thunderbird que eu uso com freqüência.