If it plays 3gp videos (which most PDAs and Cell phones do) then you can use QuickTime Pro to do that, and possibly even iMovie if it will import your videos.
So long as they play in QuickTime, yes. 3gp movies have set resolutions specifically designed for phones and PDAs, but in case you wanted another format, then the answer is yes. QuickTime allows you to fine-tune your movies in great detail.
There is a custom option for resolution, but is sometimes grayed out, depending on format used I guess. If this quicktime doesn't work, ffmpegX is more versatile (but sometimes just doesn't do anything).