Is it possible to sync two iPhones with different service providers via iCloud?
This is exactly what iCloud (and MobileMe did in the past) does for contacts.

Unless your company phone uses a company supplied directory (in which case just connect your personal phone to the company directory) you can sign up for a free iCloud account and store your contacts on both the devices in the cloud.

You could also sync from iCloud to a computer (PC or Mac) as well to an iPad, but you don't have to and can simply use it to sync the address book contents between the two iPhones.