MPEG2 for DVDs, DIVX for the best compression(say just for your comp)
As for software, i wouldn't know. I would expect Windows Movie Maker to have different ways to compress, but I don't use that. WAY too simple for what I use. As for MEPG, TMEPG(or something like that) costs a bit, but will convert to MPEG2.