If storage space isn't a problem, go for high bitrate MPEG1. It plays back very well in mplayer, but you have to use much higher bitrates for good quality. Example, I can make an very good quality 800x480 video play smoothly on the Nokia in MPEG1, but for similar quality to WMV or h.264 it's going to be over twice the file size and won't have a chance of playing on the Nokia.

#EDIT- when I said it's going to be over twice the size, I meant the high bitrate MPEG1 will be over twice the size of the WMV or h.264, but both of those formats won't play well on the Nokia.