I've always just opened the image file in photo shop and edited it there. That way you're not worrying about what level of compression the image is being saved at.
But I'd like to know if there are any other formats available....
You could always try Kunvert or DropJPEG. They're great little utilities. They each let you drop a screenshot file onto their icon and they spit out a JPEG in return. They help make up for Apple's insistence on using PDF as OS X's sole screenshot format.
When JPEGs can be viewed so universally (ex. within Hotmail and most any e-mail program) why do screenshots require conversion? It's another step that makes it harder for Mac users to display the beauty of OS X to people who may not use it.