apt-rdepends saith "sim, você pode ter Nautilus sem samba. Mesmo sem tango. Você quer fritas com ele?":
$ apt-rdepends nautilus|grep -i samba
Reading package lists... Done
Building dependency tree
Reading state information... Done
Apenas com certeza:
sudo apt-get install --no-install-recommends --simulate nautilus
Não há samba para mim no Xenial 64. Tente você mesmo. Se não houver uma surpresa, faça novamente sem o "--simulate" se você quiser nautilus.
O comentário de Steeldriver re recomendar vs. depend é totalmente direto ao ponto - o "--no-install-recommends" evita coisas que você não precisa ter. Estritamente falando, o samba em si não é nem mesmo uma recomendação para o meu sistema - acabei de expurgar o samba para testar por curiosidade. Mas samba-dsdb-modules e samba-vfs-modules são. Ainda não depende embora.
Eu nem sei ao certo por que eu tinha samba, porque ele não arrastava nada do que eu lembrava de usar com ele quando eu removia o samba. Eu acho que vou deixar isso. Fico feliz por ter entrado nesta discussão.
Espere um segundo - vejo que você já tem Nautilus. Você tentou:
sudo apt-get purge samba
ou até mesmo
sudo apt-get purge samba*
?
Isso deve ser feito sem usar o Nautilus. Se ele usar o Nautilus, basta reinstalar o Nautilus com o --no-install-recommends conforme descrito acima.