Well, you're going to have a serious problem no matter what you use to edit them. JPEGs use a lossy compression format (that is, some image data is sacrificed in the name of file size), and without going in to too much detail, at lower levels the image is blurry and hard to distinguish. There's not much you can do about this, that's just the way the format works. You can try using a paint program with a sharpen filter, this might help.
As for converting to gif, depending on the image dithering of your editing program, a gif can come out much worse looking than a JPEG because gifs only support 256 colors while a JPEG can use up to truecolor. If you convert a gif to JPEG, it will look really bad--not only will it have (up to) 256x less color data, it will be recompressed over the original JPEG, making it look even worse.