Try the latest VLC it has a converter built-in, and it's free.
Settings: video h.264 / audio acc 128 or less
crop or resize @ ***x360 and select mp4/mov container
(btw this is the first built-in preset except for the resizing options)
Anyway if the file isn't too large and is a divx/xvid avi or a h.264 mp4/mov, there's no need to reconvert it, just put it on the phone and enjoy.
Dear Nokia N8 user:
You can try out this program is good ImTOO MPEG Encoder ultimate. You have to convert your video file to MP4 format with resolution 720*480. Take a look to the attachment file .