Firstly, record at the best quality that you can. If you're going to compress afterwards then garbage in=garbage out. Edit your footage into what you want to submit without reducing quality. Hopefully you've now got a video you're happy with but a filesize you're not.
Then get yourself some software to remake the video in a reduced form. I use Super because it's good and because it's free. There are lots of others.
So take a look at how other people are doing this. Martin Madsen has had the largest file size for both VFs 12 and 13 whilst slipping under the 20Mb limit. Using an analyser like GSpot we can see his VF13 entry:-
- 1280x720 @ 25fps
XVID 1.1.2 video codec, 1690kbps
MPEG-1 audio codec, 44.1kHz, 128kbps
- 640x480 @ 30fps
MPEG-2 video codec, 1728kbps
MPEG-1 audio codec, 44.1kHz, 192kbps
So Martin gets a higher resolution video for (about the same file size) by reducing audio quality a smidge, a lower frame rate (his video is 7 seconds longer but has 10% less frames), slightly lower video bitrate but mostly by using a more efficient codec. XVID is well regarded but usually needs a download to play with Windows Media Player (although VLC handles it OK). This can be a problem for some people.
Of course, higher resolution doesn't necessarily mean a better looking video and even an especially pretty video isn't going to help you in VF if the flying isn't up to snuff. Super is very good for making multiple tries at seeing how to balance file size and quality (I convert a lot of films to fit a Pocket PC screen) and it's a completely black art. For VF I would have hoped that "good enough" would be just that.