Ogg/Theora Video would be perfect to implement with Game Editor. As far as I understand the license is free. It has been used in the GledPlay project which has since died.
GledPlay: http://www.pocketmatrix.com/forums/viewforum.php?f=61
I apologize if we are not allowed to post links.
I see that it has been mentioned that we can use animated gifs. Since I haven't bought Game Editor yet, is it possible to play the animated gifs on a Pocket PC?