Well this would depend on your actual requirements. If you are using a video script such as Clipshare or any youtube clone, you are definitely going to need FFMPEG, Mencoder, Mplayer, FLVTool, etc... This is already included in hosts that specifically specialize in "ffmpeg hosting".
Diskspace will be a factor depending on the size of your videos, pictures, and mp3 combined. Bandwidth would become a factor depending on both the size of the files and the expected traffic for your site. You would want to have some kind of leech protection if you are very limited on bandwidth.
The most known host IMO for this kind of environment is CirtexHosting. However, I do not hold any guarantee of the service. I used them personally before but I don't want to be the influential figure in your decision. Just please do not end up with an oversold server. FFMpeg really does take up a lot of resources to convert a video. You also want to make sure the port connection to the server is at least 100MB.
If you do not have a script already, something called "Media Max Script" will integrate all 3 functions in one, the image gallery, mp3 streaming, and video streaming. However, it will cost some $$$. You can always browse through hotscripts.com