AVI é apenas um formato de contêiner. O destinatário definitivamente precisa ter o codec instalado em seu computador. O H.264 é suportado em todos os computadores Apple modernos. O Windows 7 também suporta isso sem codecs externos, o Windows XP não, eu não tenho idéia do que o Vista pode ou não fazer, e o Linux não (exceto talvez algumas distribuições orientadas a multimídia como o Mint).
Então, se você está indo com um formato moderno como H.264, você pode facilmente escolher um recipiente moderno também, como o Matroska (.mkv). Não se preocupe se você adquirir um novo computador não funcionará, porque a instalação de codecs é fácil e a maioria das pessoas o faz, porque há muito material de vídeo por aí. Você só deve se preocupar com a compatibilidade se o destinatário for uma velhinha com medo de permitir a instalação de softwares de terceiros em seu PC ou de alguém em uma máquina da empresa, onde seja contra as regras corporativas instalar um codec. Mas então, você precisaria de algum codec muito antigo para compactação (não sei se o divX é suportado no Windows XP sem codecs, talvez você tenha que voltar ao MPEG-2) e ainda não há um codec que é suportado pelo Linux e pelo Windows fora da caixa.