I am using mp4 and it works well maybe your Internet speed

I'm using a PogoPlug Pro and remote video streaming via 3G and WiFi hotspots works well as long as I keep the bitrate of the encoded video below the UPLINK data rate for my home's internet connection. I've got a relatively slow DSL account and the uplink runs at about 400Kbps (that's bits per second, yes, I said it was slow). Don't confuse the uplink rate with your download speeds, usually the uplink is MUCH slower than for downloads (for my DSL account, downloads run at 2.5Mbps while uploads are capped at near 400Kbps).

I encode the video using QuickTime (Mac OS X) in H.264 format (.mp4) with a target bitrate of around 300Kbps. Because of the low uplink speed I have to encode at a reduced size (320xN, where N can be anywhere from 240 to 180 pixels -- depends upon the aspect ratio of the source). I also reduce the framerate to one half the original speed (if original is 30fps use 15fps, if 24fps use 12fps). The video is optimized for streaming, don't use the "Download" or "CD/DVD-ROM" format. The exact menu path to this type of encoding is under "File>Export>Movie to MPEG-4" (using the "Pro" version of Apple's QuickTime Player 7).

For video, I also reduce the audio sample rate to either 22KHz or 24KHz (for 44KHz or 48KHz originals) and use a bitrate for the audio of either 48Kbps or 64Kbps depending upon the needs of the source (mono/stereo and whether the video needs relatively good quality music reproduction). The audio is encoded with QuickTime's AAC codec.

Using these settings I have no problems streaming from my home to a remote location (the remote device being an iPad using 3G or WiFi). The quality isn't great, but it's certainly very usable and there really aren't that many compression artifacts (well, if you look close you can certainly see them in some frames, but for casual viewing it's fine). The resolution is also low, not even SD but it still looks fairly good.

Of course, if I'm just streaming over my home's local WiFi network I can use just about any video size or data rate I want (full 720p to my iPad is no problem and I've even done 1080p to my MacBook).