Which security strategy may work for my sceario?

I need to settle on a strategy for securing (with message encryption and authentication) a service and I’d like to throw up the scenario and find out what recommendations come back from the community. The scenario is as follows:

1. I have a WinForms “Smart Client” application that consumes a WCF Service that is hosted in IIS.
2. The client app only talks to the service (i.e. consumes no other services) and the service only exists to be consumed by the client app, and probably an ASP.Net app in the near future, but that doesn’t exist yet.
3. The Server that hosts the service is in a co-located hosting facility. Most of the time the client and the service will exist on the same VLAN, however, some users will run the client from home or from a remote office that will not be on a VLAN so will be accessing the service over the web (without a VPN).
4. Performance is important, but security of the data in the messages being sent over the wire is more important.
5. The Server that is hosting the service is not currently in a domain that is trusted by the domain that the users belong to, but that could be changed if necessary.
6. Certificate Server is not currently set up, but that could be introduced if necessary.
7. I’d like to avoid installing certs on every client (mostly because I don’t know how to do this).
8. I’d like to authenticate users and derive user rolls against a database

So, given the above scenario, my first thought is to implement username token over X.509 transport. What other strategy should I consider given the scenario above

Thanks,

Greg