GIF would typically be a good choice if the text is set against a background of flat color(s) or simple vectors, and will likely result in the smallest file size. PNG24 is a great choice if the text is set against a more photographic type of background. JPEG is not a great choice when text is involved; it's best suited for photos.
The File > Image Preview... command will allow you to experiment with different formats at the desired output size.
Thanks, I've both saved as a gif and optimized as a gif, and the smaller text in the image (a map with city names) is still blurry. You can see it here: http://www.whitewatertours.com/south-fork.htm
Thinking the best fix will be to re-write the text in the smaller format...
That's a very nice looking graphic! I think that GIF was the right choice.
How about making this a lightbox-style link, where the user can click on the smaller image to see a larger version?
The problem isn't the optimization, BTW; it's the small size of the graphic. The resulting font size is something like 8px, which is not enough resolution to properly render the average typeface. In addition, you're using a display face—something meant for larger headlines, not smaller body copy. Still, I think it looks good, and it's reasonably legible.
It looks like you have extra room on either side within your layout. You could try creating a slightly larger version of the graphic that utilizes more of the available space. Otherwise, I really think that adding a lightbox-style link to a larger version (where the user won't have to leave the current page) is a good solution. If neither of those feels right, then your idea of re-writing the text in the smaller format would also be a good approach.
Actually, there's one other strategy I could have suggested here, and that's to experiment with different interpolation algorithms, available within the Image Size dialog (under Modify > Canvas > Image Size...).
The Bilinear option might be a better choice for this particular graphic. Nearest Neighbor might also work but would probably look too aliased. You'd have to experiment to see if this setting makes a significant difference or not.
Thanks again! I tried the different interpolation algorithms and they don't seem to make too much of a difference, it's already set to bicubic.
The original image (also made in 2004 or something like that) is about 1450px wide so it looks great that way, but I agree with you the text it a bold header that does not resize well - and a link to the larger image would be nice, but currently the boss wants it to be a link to the "map" page which also gives people the choice of using the "google gadget" and mapping from their location which I think is the most helpful.