"avi" is just a container format.
I assume your files are actually encoded using divx or xvid? (which commonly use the avi container, & are quite popular codecs for certain uses

)
The 360 supports:
WMV
VC-1 (based on WMV, used for HD e.g. WMV-HD)
AVC (MPEG-4 Part 10 / H.264)
MPEG-4 Part 2 Simple Profile
It will *not* play MPEG-4 Part 10 Advanced Simple Profile, which is used by divx & xvid.
What you can do, is:
a) Use something such as
Encode360 to transcode your videos to WMV, and then use Windows Media Player to stream the transcoded files to the 360 like you do the music.
b) If you have a good enough PC, use something such as
TVersity to transcode *and* stream the files at the same time.