It makes a big difference if your original image is "graphicy" or "Photorealistic"
A GIF or a TIFF is a raster graphic, that is, it is made up of discrete pixels, and if you enlarge it, the pixels get larger too (we'll cover interpolation in a moment.)
If it is a graphic with sharp edges and blocks of solid colour and type, then you may be better going the Illustrator / Freehand route and redrawing it as a vector graphic. Note that we are not talking about enlarging the original image, but starting with the original as a template only and re-creating it by redrawing the shapes and re-setting the type.
It is a pain to do if there is a lot of detail or colour graduations - auto Trace tools can help. But once it is a vector drawing, you can re-size and re-colour to your heart's content, without losing any resolution; this is because it is no longer composed of pixels, but of lines and shapes defined by equations - like a cartoon thather than a photo. (The latest issue of Layers magazine has an article about how to make a vector drawing from a photo).
OK, what if it's more photorealistic though, with lots of colour blends and soft fuzzy edges? You can increase the size or resolution of a raster graphic in Photoshop and other "paint" or "photo", the original pixels will be spread apart, with spaces in between them, and the program will try and fill in the spaces with its best guess at what colour the intervening pixels should be. This is called "interpolation", and there are various formulae to calculate the best guess. Generally, these do a good job of smooth areas of colour, and less well on sharp edges and patterns - which get blurry. It also tends to accentuate any noise, 'dirt' or grain in the original.
If you are trying interpolation, try doing it in small steps of 130 - 150% at a time, rather than giant leaps. Also - enlarge it by steps to about 2 x your desired final size. Do not add sharpening at this time. Use the Dust and Scratches, Despeckle or Blur filters to smooth out the grain and noise in the enlarged image. It will look a bit fuzzy but more pleasant. Now scale it down to your desired size. This will gain back some apparent sharpness and detail. Now, at the very last, add a judicious amount of Unsharp Mask or Sharpening. Try to avoid visible halos around objects. (remember too you can use the Lasoo tool and Selection: feater to choose specific areas to blur or sharpen).
If there is type in the graphic, you might still consider re-setting it. Your readers will pick out flaws in type very quickly. In Photoshop, use a Layer to paint in a patch over the existing type and then a Type Layer for your new words, matching font, size and spacing as close as you can. You can pick up the original text colour with the eyedropper tool. Edit non-destructively -- Keep all your layers so you can come back and edit again. You may have to rasterize (a copy of) the type layer and blur, colour adjust or distort it some until it matches the underlying image.
If you can spend a bit, get the Genuine Fractals plugin from -- Lizardsoft? -- it does a much better job of creating an interpolated image even at extreme magnifications.
Thanks
Trevor
CanadaRAM.com