I’d like a map of the world. Ideally a political map in simple outline, in jpg, gif, or png (no PDF!) Best of all would be one with a well-documented projection, so that you could in principle map from image coordinates to latitude/longitude (but that’s asking a lot). This is harder to find than I thought it would be — any pointers appreciated.
Open-source maps?
Tim Converse 
Have you looked at http://www.lib.utexas.edu/maps/index.html ? More public domain maps than you can shake a stick at. Many in PDF, but many in GIF, JPG, etc. – many scans of somewhat older (ie., 2002) paper maps.
http://worldatlas.com/webimage/testmaps/maps.htm might also be of use, though not all images are public domain.
If you have a copy of Photoshop and/or Illustrator, you should be able to use a PDF, anyway, as they have built in support for PDF (PDF being from Adobe and all.)