I found out how to do it, it just isn't documented that I could see.

The billing address is sent as part of the payment profile, not separately like the shipping address.  It was the ->billTo part that I was missing.

$customerProfile = new AuthorizeNetCustomer;
    $customerProfile->description = "Description of customer";
    $customerProfile->merchantCustomerId = 123;
    $customerProfile->email = "user@domain.com";
    
    $paymentProfile = new AuthorizeNetPaymentProfile;
    $paymentProfile->customerType = "individual";
    $paymentProfile->billTo->firstName = "john";
    $paymentProfile->billTo->lastName = "Doe";
    $paymentProfile->billTo->company = "John Doe Company";
    $paymentProfile->billTo->address = "1 Main Street";
    $paymentProfile->billTo->city = "Boston";
    $paymentProfile->billTo->state = "MA";
    $paymentProfile->billTo->zip = "02412";
    $paymentProfile->billTo->country = "USA";
    $paymentProfile->billTo->phoneNumber = "555-555-5555";
    $paymentProfile->billTo->faxNumber = "555-555-5556";
    $paymentProfile->payment->creditCard->cardNumber = "4111111111111111";
    $paymentProfile->payment->creditCard->expirationDate = "2015-10";
    $customerProfile->paymentProfiles[] = $paymentProfile;
    
    $response = $request->createCustomerProfile($customerProfile);

Hopefully someone else finds this useful (and it would be nice if this was reflected in the CIM.markdown documentation).