Comparar filas y columnas de la misma tabla

¿Qué tal usar un join? ? A continuación se muestran todos los pares que son diferentes:

select tb.*, ts.*
from company tb join
     company ts
     on tb.company_name = ts.company_name and
        ts.address_type = 'shipping' and
        tb.address_type = 'billing' and
        ts.address <> tb.address;

Si solo quieres las empresas que son diferentes:

select company_name
from company t
group by company_name
having count(distinct case when t.address_type = 'billing' then address end) = 1 and
       count(distinct case when t.address_type = 'shipping' then address end) = 1 and
       (max(case when t.address_type = 'billing' then address end) <>
        max(case when t.address_type = 'shipping' then address end)
       );

Nota:esto también verifica que solo haya una dirección distinta de facturación y envío.