Remoting will be easier than direct sockets. Romoting and direct sockets will have the same issues with configuration of the firewall. Based on the restrictions you have mentioned, remoting over tcp seems like the most workable solution. Webservices would be the easier way. Remoting over http is similar to webservices, but if you can't run iis on the other side, neither will work. Another option would be to run an ftp server on the other side but if they are reluctant to install iis then ftp is likely not an option either.
http://blog.darrenstokes.com