Streaming or stored video files, basically you can use the same parameters and the same tools. I describe streaming only.
Use VLC to stream the video via Wifi or Edge to your phone.
An excellent client is Coreplayer (only 20 bucks)
On VLC set transcoding params like this:
video codec: mpeg4 (alternatively you could use h264)
video bitrate: 300-400kbs (wifi) ; 100-200kbs (edge)
audio codec: mp3
audio bitrate: 48-64kbs
container: ts (transport stream)
VLC can stream everything including live TV from TV/Sat cards and also from settop boxes.
If you wonna play files from memstick transcode your videos to files with the wifi parameters.