Getting the maximum performance out of the API requires following a few simple rules.  The main difference is that you are going over a Wide Area Network, so network times will be higher. 

We have spent a significant amount of time desiging our API for optimal performance.   Please follow the following guidelines when using the API

1. Most calls are bulk calls (they can take more than one record).  Do not sit in a loop calling create with just 1 account, batch them up and pass 200 accounts to create in one go.  Loading 1,000,000 records can be done in 5,000 calls or 1,000,000 calls.  Doing it in 5,000 calls will dramatically improve performance
2. Get familiar with the retrieve call.  If you are pulling data from related tables, the retrieve call is a high performance call that you should be using
3. Cache metadata, if you're using the describe* calls a lot, cache the results of each call for the duration of the session.
4. Make sure you're using HTTP/1.1 persistent connections, every time you create a new connection, you have to go through the SSL setup again, persistent connections allows you to aggregate that SSL setup code over multiple requests. (If you're using Axis, this means ditching the default HTTPSender, and using the superior, but not default commonsHTTPSender class instead)
5. Use compression, unless you have an OC45 connection into the back of your machine, compression will help reduce transmission times, the Sforce API supports gzip and deflate compression for both request and response.
6. Consider a local lookup cache.  If you are constantly doing lookups, you should consider a local lookup table.   
   
   See these tech notes for help on compression:
   
   SOAP Compression in Visual Studio
   Enabling SOAP Compression in Java with Apache Axis