Nokia has released Nokia Video Manager for Windows PC. The software helps you copy videos to your phone and transcodes them on the fly (converts them to an optimal format). Nokia Video Manager supports conversion from avi, mpeg, wmv and mov (DivX, XVid, MPEG-2 and Quicktime codecs) to mp4 (H.264). As such it is only compatible with devices that can play back the H.264 format.
Current S60 phones that are capable of playing H.264 are the the N75, N76, N80, and N93 (unconfirmed - some may require a firmware update) [Update: support for H.264 does not seem to guarantee playback, see the comment thread] and all S60 3rd Editions Feature Pack 1 phone - N95, Nokia 6290, Nokia 6110 and Nokia 5700. Officially only the 6290, 6110 and 5700 are supported, but that may be because the tool comes from the Mobile Phone rather than the Multimedia group.
H.264 is a good format to use because it is noted for achieving high data compression rates - this means it will result in smaller video files than other formats at the same quality level. It is the same format used in videos for Apple's iTunes service
http://nokia-video-manager.en.softonic.com/symbian/download