O seguinte irá quebrar em arquivos contendo novas linhas, mas deve funcionar o resto do tempo. Ele classificará os arquivos com base na hora da última modificação, e não no tempo real de criação, porque o Ubuntu não armazena o tempo de criação dos arquivos. Então, se você modificou os arquivos desde que os baixou, não obterá uma ordem precisa.
n=0; ls -tr | while read i; do n=$((n+1)); mv -- "$i" "$(printf '%03d' "$n")"_"$i"; done
ls -tr ordena arquivos por hora de modificação, o mais antigo primeiro (e quando você canaliza a saída de ls ele lista automaticamente os arquivos um por linha, em vez do modo padrão de fazer as coisas - deve ser notado que é um GNU-ism, se você tiver que trabalhar em outro * nix com uma versão diferente de ls , isso pode não ser o caso. while read i pega essa lista e passa por cima de cada item, um de cada vez, e o resto faz a renomeação real.
n=$((n+1)) incrementa a variável $n em um. Poderia haver problemas se isso tivesse sido definido de antemão, então, para estar no lado seguro, você deve defini-lo como 0 no início da linha.
$(printf '%03d' "$n") imprime o número contido na variável $ n, preenchido com três zeros (portanto, 001, 002 ... 087 ... 999). Espero que o comando mv seja bastante óbvio.