Eu começaria normalmente e usaria "renice" depois ...
No entanto, eu pude fazer um rápido hack com "su", que funciona:
sudo nice -n -20 su -c command_to_run user_to_run_as
(Se você não tem que dar uma senha ao sudo - talvez porque você já tenha acabado de dar - você pode adicionar um "&" para colocar tudo em segundo plano.)
Como você já é root com o comando sudo, o su não lhe pedirá uma senha. Consegui iniciar um programa-X a partir de um emulador de terminal em X. Se você quiser executar o programa-X como outro usuário que não o usuário que possui a sessão-X, provavelmente precisará informar explicitamente ao X para permitir isso (aberto para clientes X daquele usuário).