Preferably with a completely different provider, in case something takes out there entire network somehow (or they go out of business).

But make sure you check where the other provider is hosted: I read it one user (individual, not a startup or other company) who had backups of stuff on a shared host with a second shared host. It turned out that they were both running on servers in that one OVH DC and they were cheap hosts with no better backup/dr plan themselves...