Update: I looked into it, my phone's specs claim to have: "Video Player for MP4, 3GP, 3G2, WMV Formats" and apparently records in "3G2 format." Hopefully one of these video converters should do the trick!
Hmk, I'm giving SUPER a try, and I think I understand how to work it. Anyone have any suggestions on what filetype/which encoding type/etc I should use to get the most decent video quality but smaller end filesize? I'm giving mp4 format with mpeg4 encoding a try, but just incase someone knows before I spend time trying everything, please let me know!
Another update. I took a 174MB .avi file originally at the resolution 512x384, 30fps (I think) and converted it to .mp4 at 320x240, 25fps and it gave me a 114MB file.

I was hoping for better.. wishful thinking??