I'm not into cell phones, so I don't know, but I can tell you what to look for: anything that supports mp4 file playback and H.264 video (also known as AVC and MPEG-4 part 10). It should be able to play 320x240 H.264 and 512x384 basic MPEG4 video.
Also, no device but an iPod can play movies bought from the iTunes Music Store, since they use Apple's DRM.