• Library of Congress Prints & Photographs Collection -- There are over 100,000 historical images on this site.  USE CAUTION; not all of them are copyrighted, but when you click on an image link it will take you first to an imformation page that clearly states the copyright status of the image.  Occasionally you'll run up against one that says "status not determined," but those are usually the really old images, and images created before 1923 are out of copyright no matter what their original status was.  LOC has many of the old standbys but also some really obscure stuff, so if you want a historical image you're probably in luck.
• Art Renewal Center -- Lots and lots and lots of old art, all okay 'cuz it's before 1923.  I did a search for Monet and found 128 images, which is more than enough to encompass all the famous pieces and then some.
• Fromoldbooks.org -- Just what it sounds like -- high-quality scans from old books, all out of copyright.  Use it just like Google Images, with keyword searches and the whole shebang.  Check out their photo collection of ruined castles.
• Yotofoto -- Maybe the best site out there for just stuff, absent a specific context.  Like Google Image Search, but it's all free. :) I did a search for "war" and came up with over 1500 images, many of which would look great here at Kos.  [Update]  Here's the fine print: "While some of the images are in the Public Domain, most are released under Creative Commons, GNU FDL or similar licenses. These licenses typically have some minor conditions of use (such as requiring that credit be given to the photographer)."  So USE WITH CAUTION -- you may have to provide attribution to anything you use from this site.
• National Atlas Congressional District Maps -- If you ever want to put up a picture of a CD map, they're all right here, free of charge.  National Atlas has all sorts of other useful maps as well, all free of charge.
• FirstGov -- Not an image repository, but a link to all government image repositories.  Despite the disclaimer at the top, the general rule is this: if the photo belongs to the U.S. Government, then it belongs to YOU and you can use it as you wish.  ALWAYS CHECK, but you're pretty safe here.  Some popular sites from this collection include Visible Earth and NIX, both from NASA, Fish and Wildlife Service, and USDA Agricultural Research Service, all of which should be safe to use.
• UTOPIA -- Public-domain portraits of historical figures, in alphabetical order.  Some weird ones here too, which is great.  NOTE: This site appears to be going dark in the fall of this year owing to lack of funding, so get what you want now!
• TeachPol -- Hundreds of images of political history.  There are some really important events in here -- I guarantee you'll find the collection extremely interesting.  You can't find these in Google Image Search either.
• New York Public Library Digital Image Gallery -- There are over 500,000 images in this online collection, which makes it five times as big as the Library of Congress's.  Having been to NYPL, I can say that they ALWAYS do everything better than everyone else. :)  I searched for "Kurdistan," which I thought would be pretty hard to find anything about (given that it never actually existed as a separate country), and turned up five fantastic images, all relevant.  Noodle around with this and see what you think, but BE CAREFUL -- there may be fees associated with certain images.

[Update]  Sites suggested after this come from folks in the comments, not from me.  I will continue to update this list as the suggestions come in (though in fits and starts):

• GIMP-Savvy -- Indexes photos from NASA, NOAA (National Weather Service), and the Fish and Wildlife Service in one convenient search engine.  The NASA photos are particularly nice -- I searched for "war" and found some really pretty photos.
• Web Gallery of Art -- another good resource for old art, completely kosher because they don't put up pieces from after 1850.  The images are high-res and gorgeous.
• EveryStockPhoto -- This one is REALLY nice, and NOT listed on Wikipedia.  The site boasts over 380,000 free stock photos, with no usage restrictions (unlike Yotofoto; see above).  I strongly recommend this site.
• Openphoto -- CREATIVE COMMONS LICENSED, which means you need to cite the photographer when you use it.  Also, beware the search engine -- I did a simple search for "war" and got a photo of a WWI-era soldier, but also images of plants, circuit boards, and soda cans.
• Flickr Creative Commons Pool -- USE WITH EXTREME CAUTION; these photos are under different kinds of Creative Commons licenses, which are clearly marked but can be really confusing if you don't understand Creative Commons.  Only use if you think you know what they're talking about.  On the flip side, there are literally tens of millions of images here -- by far the biggest archive identified so far.
• Archive.org -- Not really for images, but great historic video and audio collections, whose copyright status is clearly marked.  An excellent resource.
• Indymedia -- News photos of current events are posted here and at several subsidiary sites (linkable from the main page) under a Creative Commons license, which means post WITH ATTRIBUTION.  This is a fantastic resource, though, for folks who want news photos for their diaries.
• MorgueFile -- An excellent and exhaustive database of surplus stock photos.  One I'll probably use a lot.  Remember to USE WITH ATTRIBUTION, otherwise you're violating their copyright.
• Dover Clip Art -- Just what it sounds like: free clip art from Dover, one of my favorite publishing houses.  You have to sign up for a weekly e-mail digest to use this one, but once you've done that you've got over 400,000 clip art images available for use WITH ATTRIBUTION.
• WPClipart -- Clip art optimized for Word documents, but eminently usable online.  Unfortunately, the site uses a Google interface, so you have to click through a few pages to actually see the images, but the upside is that you don't need attribution for these -- "They are truly free," says the site.  Kewl!
• Wikimedia Commons -- USE WITH EXTREME CAUTION, as the copyright status on these images varies and is in some instances unknown, which means you shouldn't use them.  Also appears to be of somewhat limited use because there is no search function.
• Stock.xchng -- USE WITH EXTREME CAUTION, as you may have to not only provide attribution for these photos, but notify the photographer by e-mail.  Luckily, that information is clearly displayed for each photo under "Usage" in the Photo Information at the right of the image.  A nice collection of free stock photos.

Keep in mind this is NOT an exhaustive list of public-domain image sites; the exhaustive list is here, courtesy of our friends at Wikipedia.  I've cherry-picked as I saw fit, and can vouch for the fact that every site I've mentioned turns up at least some really cool and relevant images.

But I'm interested to hear from you: what are YOUR favorite public-domain image sites?

Also, if someone feels like adding any of this information to DKosopedia, go right ahead; I don't know how to use the thing, so I can't help you out there.