MP4 (MPEG-4 or h.264)
You can use Ovi Suite 1, Nokia Photos or Nseries PC Suite 2 to drag-drop videos to your phone. They will be automatically converted to the recommended format if the phone will likely have problems playing them.
Or you could use some 3rd party application for the transcoding, e.g. http://portablevideo.blogspot.com/2008/03/using-su