The first thing I do when I get a new device is figure out the lowest acceptable file size of a DVDRip I can view on it. I personally use handbrake and the ipod option and have had great success. It's free, you can specify file size, it will give you the command line string so you can use it from a dos prompt (which is a tad faster) if you choose, and allows you to crop the screen to your heart's desire. I will give just two obvious but important not to forget encoding tips.
1. Audio bitrate is where you save space period. Very few times have I ever been anywhere watching a movie on my mobile device when I needed some super high quality sound. I personally use 96 or 64 for the bitrate and it is totally acceptable for me just remember that if you specify file size like it kind of sounds like you want to, the lower you make the audio bitrate, the more space you give back to the encoder to allocate to video quality .
2. Source. If you have some Xvid or DivX file that you downloaded from a newsgroup then your source is compressed and you can't expect a compression of a compression to look great video wise. Sometimes it will but it depends on what settings the original encoder of the file used and it is much easier to just use a Dvd source and count on quality.
Good Luck!