h264/x264 codecs will be the most efficient
Yep. h.264 with AAC audio is generally the best compression, although choice of audio format may not matter much if enough bitrate is used. I generally use AutoMKV for by-hand files, and Mencoder with script files takes care of most of the automated stuff. H.264 is usually around 30% smaller size than xvid.
There are other things to consider. H.264 should be in an .mp4 or .mkv container. You can put it in an .avi, but it's not recommended, and any video person who sees you do it will probably think you're an idiot. If you want compatibility with a divx/avi/dvd player, then there are only so many options. H.264 also may require a halfway-decent computer to play it back and takes probably three times as long to encode. .mp4 can't use AC3 audio (which is completely stupid that it can't, but hey, I didn't create it).
Basically, depending on factors, I use xvid or h.264, and wmv for my Zune, and that's pretty much it. There's little reason to use other formats unless it's for a specific playing device such as mpeg2 for a DVD player.
You can shrink the filesize at the same quality by cutting the resolution and things like that. Just depends what your goals are with the file. Anime is generally considered the hardest media to properly convert into something else, btw. If the file sizes are already "decent," I'd consider just leaving them be. If you want to convert to put them on an ipod or Zune or something, that's a whole lot easier because great quality rarely matters so you can cut more corners.
And, yeah, on an 2200+ XP, even xvid encoding can take awhile. H.264 on my 3ghz Core2Duo often is around 25fps. Like I said, if the filesizes are already decent, you may not want to bother.
Also, if for some reason you'd want to edit the files later, xvid in a .avi is the easiest. It can be a big pain to cut commercials or whatever out of even an mpeg, much less something in an .mp4 or .mkv container. And with xvid/.avi, you can still use good ol' VirtualDub, which generally isn't recommended at all for other formats. It can do it, but it's along the same lines as putting h.264 in an .avi, it's all hacked up and can cause playing problems later, etc.