With .Net what is the best way to interact with a service (i.e. how do most tray-apps communicate with their servers). It would be preferred if this method would be cross-platform as well (working in Mono, so I guess remoting is out?)
Forgot to mention, we still have to support Windows 2000 machines in the field, so WCF and anything above .Net 2.0 won't fly.
Be aware that if you are planning to eventually deploy on Windows Vista or Windows Server 2008, many ways that this can be done today will not work. This is because of the introduction of a new security feature called "Session 0 Isolation".
Most windows services have been moved to run in Session 0 now in order to properly isolate them from the rest of the system. An extension of this is that the first user to login to the system no longer is placed in Session #0, they are placed in Session 1. And hence, the isolation will break code that does certain types of communication between services and desktop applications.
The best way to write code today that will work on Vista and Server 2008 going forward when doing communication between services and applications is to use a proper cross-process API like RPC, Named Pipes, etc. Do not use SendMessage/PostMessage as that will fail under Session 0 Isolation.
http://www.microsoft.com/whdc/system/vista/services.mspx
Now, given your requirements, you are going to be in a bit of a pickle. For the cross-platform concerns, I'm not sure if Remoting would be supported. You may have to drop down and go all the way back to sockets: http://msdn.microsoft.com/en-us/library/system.net.sockets.aspx
Have your service listen to 127.0.0.1 on a predefined port with a plain old TCP stream socket. Connect to that port from your desktop application.
It's dead simple and it's completely cross platform.
Most services that have a GUI component are run as a named user, and are allowed access to the desktop. This lets you access it via COM or .NET but only locally (unless you want to get complicated)
Personally, I open an ordinary old socket on the service - its cross platform, allows multiple clients, allows any app to access it, doesn't rely on Windows security to be opened up for it, and allows your GUI to be written in any language you like (as everything supports sockets).
For a tray app, you'd want a simle protocol to communicate - you might as well use a REST style system to send commands to it, and stream XML (yuk) or a custom data format back.