Your video output looks so bad because of the low quality setting specified in the render output.
First Things first:
You should never render out your 3d renders as movie files, NEVER! The reasons for this are:
The only time when you would want to render out a movie in blender is when you have an ready rendered animation as an image sequence and you want to convert it to a single movie.
The proper way:
Render out your animation as an image sequence. The output files should be a very high quality image which is why I would use either: png, tga, exr or whatever will yield a good looking image
In the blender Video Editor load the image sequence as an image sequence.
Now render out as a movie
Back to the actual question. You need to increase your render settings. Here are the important parameters you need to consider increasing:
Format
Bitrate: The target amount of data per second in your video file
GOP: The number of key frames for the color palette. A value of 10
means that during those 10 frames all are drawing frames based on the same 256 colors. If your scene is changing color during this time the quality will suffer.
Rate
I think in your case the following settings would yield satisfactory results