People have got 720P HD to play at 500K. Its all based on how good your source material and how good your encoding skills are.
Take a look at the demo on
http://www.flashvideofactory.com/tes...H264_500K.html
As for Codec, its either H264 or VC1
http://on10.net/blogs/benwagg/Hands-...ll-Stars-Redo/
Talks about why VC1 is better
Jay