If you just want to take screenshots, I use
IrfanView. Basically when you hit Print Screen the entire screen gets pasted onto the clipboard, and you can paste it in any program using Ctrl + V.
The reason JPEGs come out so crap in paint is probably because in their infinite wisdom Microsoft decided to se the compression quality to high, making the picture look terrible.
IrfanView allows you to change the compress/quality factor - leaving it at 80% usually produces nice results.