Movies have a different grain/compression to them than images. You are doing the right thing to render out to an image sequence. You just need to increase the quality of your movie output. Depending upon the movie type (MOV,MPG, MP4, OGG, AVI etc…) there are different quality options. A general cross platform video container is MP4. If you don’t have the free xVid codec installed, I recommend getting it.
The best option is to use standalone codecs. There is MeGUI with x264 and xVid if you like to do that. Render to sequence, then encode with megui - you can use one of presets or tweak codec’s options on your own (but you should know clearly what are you doing).