File size is always an issue on a mobile device. You should convert your videos to smaller screen sizes to save space. A more serious issue is compatibility. I tried to play a bunch of my AVI files on the storm but with no cigars. So transcoding video files was a necessity.
There are a bunch of utilities for Windows to convert videos to a variety of formats but nothing equivalently easy exists on Linux. Or so I thought.
Then I discovered that Tablet Encoder (perl script) for the Nokia Maemo platform works equally well for encoding videos for the Storm! Infact I realised that the default options for conversion to MPG give you a decent enough video playback. So you can just do this -
./tablet-encode original_movie.avi converted_for_the_storm.mpgand you are done.
It squishes a 1.5 GB movie into a 300 MB filesize with very decent audio and video quality. Try it!