Разнес сериализацию/десереализацию на сервер и клиент.
Получил увеличенное время десереализации по сравнению с тестовой программой.

На моих данных в тестовой программе было ~ 2.8 сек, на клиенте получил ~ 4.5

Код на клиенте:
Int32 arLen = 0;
byte[] ar = MyRemoteObject.GetData(ref arLen);

byte[] arUnZip = new byte[arLen];
ZipBase.Uncompress(arUnZip, ar);

MemoryStream ms = new MemoryStream(arUnZip);

timer.Start();
DataSet dsLoaded = DataSerializer.DeserializeDataSet(ms);
Console.WriteLine("Deserialization time:{0,5:##0.0000}",timer.Finis());

С чем это может быть связано?