personnellement j'utilise soit un serveur perso auto-hébergé soit celui du boulot et le plus souvent ma sauvegarde se fait en réseau local. L'important est ici d'avoir un accès ssh. Il est même possible d'utiliser un disque externe, NAS branché sur le routeur…
Pour les hébergement tiers je n'ai pas de proposition particulière à faire, n'importe quel hébergement classique avec accès ssh fera l'affaire, il faut peut être aussi voir du côté d'ubuntuone et autres solutions de sauvegarde (qui de surcroît proposent leur propre système de sauvegarde).
Enfin je tiens à signaler l'existence du logiciel
back in time qui est basé sur [doc]rsync[/doc] et permet de faire des sauvegardes incrémentielles.