On one server I have a Windows service that is dependent on a Windows service on another server. Is it possible to set up a dependency like this?
What you mean by setting up a dependency? If you have a service that relies on a service on another server then you'll have to use something to monitor the status of the service that is relied on.
Assuming service 2 relies on service 1 running on it's server. If service 2 fails when service 1 fails, then you can script a command to start service 1 and have that run when service 2 fails after 3 retries.
If service 2 doesn't necessarily fail, then you should use something like Solarwinds Application Performance Manager (expensive) or IPSentry (inexpensive) to monitor the status of service 1 and execute a start script if service 1 dies (or at the least e-mail/page you).