Need advice on what program is the best and what kind of file size or compression I can expect.

Would it be better to convert the file to another format and then attempt to shrink?

You can get a utility called avicodec which will be able to tell you what codec was used to encode the file. There are a lot of options but what I believe is that divx is probably the best. You can download the divx codec and get virtualdub then use it to encode the file and see if it gets smaller.