This image looks like it should be a JPG or PNG, rather than a GIF.
At this low resolution, rasterized text as part of the image will never look good. It should be live text on top of the image. Photoshop is not a suitable tool for this - it will rasterize everything to the base resolution.
If it's absolutely unavoidable, use PNG.