Что лучше в качестве backup-сервера — Samba или NFS?

NFS - родной для Linux протокол, самба - родной для винды.
NFS - нативнее поддерживает файловые системы Линукс, samba - конвертирует.
NFS - будет заметно быстрее на множестве файлов, но передача крупных одиночных файлов в принципе сопоставима. Скорее всего замедление именно из-за работы с файловыми аттрибутами и правами доступа.

Я бы рекомендовал nfs.

Рекомендую поставить urbackup.org , особенно если сеть небольшая.
Все будет делаться автоматически, сервер есть под линукс, клиентов, практически под все платформы.
PS. Ну, или оставить самбу, в nfs могут теряться разные атрибуты, которые несовместимы с ntfs. В самбе они правда тоже теряться могут.
Так что лучше ставьте ПО для бекапов, которое будет правильно сохранять атрибуты.
PPS. Ну и если сильны духом, то можно и bareos развернуть. Тоже есть клиент под виндовс.

И да, и тем и тем пользуюсь, bareos стоит на кластере, а urbackup в офисах.

ленточный накопитель

лучше rsync. Он эффективней передает файлы по сети, поблочно сравнивает, передает только изменения и тд. На этом протоколе куча решений резервного копирования.