AVI is only a container format. The recipient definitely needs to have the codec installed on their computer. H.264 is supported on all modern Apple computers out-of-the box. Windows 7 supports it too without external codecs, Windows XP doesn't, I have no idea what Vista can or cannot do, and Linux doesn't (except maybe some multimedia-oriented distros like Mint).
So if you are going with a modern format like H.264, you can easily pick a modern container too, like Matroska (.mkv). Don't worry that if you get a new computer it won't play, because installation of codecs is easy and most people do it, just because there is so much video material floating around. You should only worry about the compatibility if the recipient is an old lady afraid to let you install third-party software on her PC, or somebody on a company machine where it is against corporate rules to install a codec. But then, you'd need some very old codec for compression (I don't know if divX is supported on Windows XP without codecs, maybe you'll have to go back to MPEG-2) and there still isn't a codec which is supported by both Linux and Windows out-of-the-box.