How to check if billing and shipping address are equal?

Use array_diff.

$order = $invoice->getOrder();
$billing = $order->getBillingAddress()->getData();
$shipping = $order->getShippingAddress()->getData();

$diff = array_diff($billing,$shipping);

ref: http://us3.php.net/array_diff

you may have to strip out some of the data of each array, before the diff. I am sure you can work it out ;)

Okay, so here's my attempt following ProxiBlue's suggestion:

$excludeKeys = array('entity_id', 'customer_address_id', 'quote_address_id', 'region_id', 'customer_id', 'address_type');
$oBillingAddress = $order->getBillingAddress()->getData();
$oShippingAddress = $order->getShippingAddress()->getData();
$oBillingAddressFiltered = array_diff_key($oBillingAddress, array_flip($excludeKeys));
$oShippingAddressFiltered = array_diff_key($oShippingAddress, array_flip($excludeKeys));

$addressDiff = array_diff($oBillingAddressFiltered, $oShippingAddressFiltered);

if( $addressDiff ) { // billing and shipping addresses are different
    // Print stuff
}

Basically I'm stripping out some keys by using an $excludeKeys array, so array_diff will be comparing only the relevant data. To strip out several keys without having to create a loop, I'm using array_diff_key in combination with array_flip to get rid of the unnecessary array keys.

Improvements and feedback welcome. :)

Even though there is already an accepted answer, I'd like to share this solution I saw (similar) once in a 3rd party module:

function serializeAddress(Mage_Sales_Model_Quote_Address $address)  {  
        return serialize(
            array(
                 'firstname' => $address->getFirstname(),
                 'lastname'  => $address->getLastname(),
                 'street'    => $address->getStreet(),
                 'city'      => $address->getCity(),
                 'postcode'  => $address->getPostcode(),
                 //add the attributes you want to check for here for ex. company,...
            )
        );
}

Which was then called:

$shippingAddress = $invoice->getShippingAddress();

if (!$shippingAddress->getSameAsBilling()) {

     $shippingData = $this->serializeAddress($shippingAddress);
     $billingData = $this->serializeAddress($invoice->getBillingAddress());

     if (strcmp($shippingData, $billingData) != 0) {
        return false;
     }
}