Você observou corretamente que o problema é o > redirect. Duas soluções:
Use algo assim:
find . -type f -name "*.ext" -exec sh -c "head -c 128 '{}' > ~/Desktop/heads/'{}'" \;
Ou você também pode passar o '{}' como um argumento para o subshell da seguinte forma:
find . -type f -name "*.ext" -exec sh -c 'head -c 128 $1 > ~/Desktop/heads/$1' -- {} \;
O último funciona porque -- {} passa o nome do arquivo como um argumento para sh -c , que pode ser acessado por $1 . Observe que você agora teria que usar aspas simples em ' em vez de aspas duplas.
Atualização: Eu encontrei uma pergunta sobre estouro de pilha que cobre o problema subjacente, usando > dentro de xargs ou comandos semelhantes:
How to use > in an xargs command?
I want to find a bash command that will let me grep every file in a directory and write the output of that grep to a separate file. [...]