For my storm 2, I use mpeg-4. I rip my movies to be the best possible so the files are around 1-2gigs. Some think its kinda big, but I like the picture quality to be good and not washed out. Besides the movies don't stay too long on the phone. Once I finish watching them they are removed.
Posted from my CrackBerry at wapforums.crackberry.com