The BlackBerry records videos in 3GPP format (.3GP extension), which isn't the most portable format. If you send a .3GP video to someone, the odds aren't great they'll be able to play it. Xvid, with an encoding example below, isn't most portable either, but VLC will play it on all platforms, recent versions of Windows Media Player support it, and QuickTime on OS X will play it with the Perian components installed.
FFmpeg is a fantastic cross-platform audio/video encoding solution. In fact it's so good that many commercial applications like to use it without paying license fees to the appropriate patent holders.
Download Windows ffmpeg binaries from http://ffmpeg.arrozcru.org/autobuilds/
On some Linux distros, like Ubuntu, you'll likely need the -unstripped builds.
When quality is not a concern – and with such a low quality source, it isn't – you let ffmpeg use it's default settings without issue. Codec names will vary based on the age/version of your ffmpeg build. Run ffmpeg -codecs to see all the available codecs. If you want to keep the video bitrate the same, pass the -sameq parameter to ffmpeg.
Convert .3GP to Xvid
libxvid may just be xvid, and libmp3lame may be called mp3 instead.
ffmpeg -i MOVIE.3GP -f avi -vcodec libxvid -acodec libmp3lame MOVIE.AVI
A 4.3 MB .3GP file was encoded to a 783 KB .avi, 82% reduction in size.
Convert .3GP to MPEG1
ffmpeg -i MOVIE.3GP MOVIE.MPG
A 4.3 MB .3GP file was encoded to a 910 KB .mpg, 79% reduction in size.
Convert .3GP to standard MPEG4
ffmpeg -i MOVIE.3GP MOVIE.MP4
A 4.3 MB .3GP file was encoded to an 825 KB .mp4, 81% reduction in size.
Convert .3GP to standard Windows Media 7
ffmpeg -i MOVIE.3GP -vcodec wmv2 -acodec wmav2 MOVIE.WMV
A 4.3 MB .3GP file was encoded to an 885 KB .wmv, 80% reduction in size.