The delay that is experienced when a client is calling a webservice for the first time is caused by the fact that by default a XmlSerializers dll for the webservice needs to be compiled. This is causing the 2-4 seconds for the initial call. Of course this is the case when the webservice application is already running, if it’s not you would have a recycle. In which case the other answers could help.
To speed up the initial call you can create the XmlSerializers dll at compile time. You can do this by setting your project build ‘Generate serialization assembly’ to on. This generates an MyApplication.XmlSerializers.dll containing the webservice information. Now the initial call dropped to 300 ms, presumably the loading of the dll. All calls there after take 0 ms.
In Visual Studio right click on your project and choose ‘Properties’. Go to the ‘Build’ Tab. There you have an option ‘Generate Serialization assembly’ in the ‘Output’ section. If you change the value to ‘On’ the serialization assembly will be generated during compile time.