You need to make the client calls asynchronous. If you're using VS 2012, you can enable the Task based asynchronous calls in the service reference, then call via:
var task1 = proxy.PrintCustomerHistoryAsync(customerListOne, @"c:\DestinationOne\");
var task2 = proxy.PrintCustomerHistoryAsync(customerListTwo, @"c:\DestinationTwo\");
// The two tasks are running, if you need to wait until they're done:
await Task.WhenAll(task1, task2);