Eu uso o programa variedade :
sudo add-apt-repository ppa:peterlevi/ppa
e
sudo apt-get update
então
sudo apt-get install variety
Tem muitas boas opções.
Sou usuário do Wallch. A troca de papel de parede faz com que o meu 2x 2 GHx proc sufoque se o vídeo estiver sendo reproduzido no momento. Ou colocar o trabalho de programação em vez de assistir ao vídeo, o que resulta em ações atrasadas.
Eu relatei o bug para o Wallch link e parece depender do GNOME, não do Wallch.
Eu ficaria feliz em saber como desabilitar o efeito de desvanecimento para mudança de papel de parede.
Editar: por enquanto desisti e acabei de modificar a mudança do papel de parede delay para 2 horas ... Não há respostas :(.