The first call under a CF application is when all of the proxy objects on the device are created. So even if the objects, etc on the server are already spun up, the first call from each device is going to be substantially slower than any subsequent call.
A common workaround for this is to have your service expose some stub method (it can do absolutely nothing if you want) and when your application starts up, spawn a worker thread that calls this stub. This will create the service proxy objects in the background for you so when your app actually makes a call out to the service, everything is ready.