NFS is going to be easiest. Samba is a port of Windows file sharing, and because of that it has a more complex and fussy configuration, but no incredible benefits for a Linux->Linux share. I don't know SSH-FS, I assume it would be good if you want the traffic between servers encrypted, but since it will be served out to the internet, that might not be any benefit.
Setting up NFS is a matter of installing the packages, on the media server you need to "export" the folder where all the media is (by putting it into /etc/exports), and on the client you need to make a folder where you want to access the media, and mounting the share onto that folder (and put it into /etc/fstab so it auto-mounts).
What type of authentication? The "NFS is so old it doesn't really have usernames and passwords, it's just machine and IP based" authentication. Use internal IP addresses, not public ones (I assume you get a private network between the machines with Linode?).
As for what you do with a dropped connection, I don't know - I'd start with trying it and expect no dropped connections, and if they do turn up, maybe make a trigger to unmount/remount or send you an email alert. If you have a server monitoring system to pick up problems, tie into that.
If this is as I describe, then the NFS share will be on a private network between the two servers, so nobody on the internet can attack it, and nobody with a Linode server can attack it - that might be worth checking. If you have IPTables / software firewalls, then they will need updating to allow NFS through, and a quick Google suggests Lenny has SELinux installed by default, so if it's mysteriously not working when it looks like it should, check /var/log/secure (or similar) for selinux related deny messages to work on.