Old Maps Online: A collaboration that brings together over 400,000 public domain maps online. A rich federated collection with a well maintained and intuitive map based search interface. Many of the other collections listed below are available here as well, so this is often a good place to start.
David Rumsey Map Collection: Over 98,000 historical maps from the 16th to the 20th centuries. Well documented collection with good quality, high-resolution images.
Library of Congress Map Collections: Over 38,000 of the LOC's map collection is scanned and available through their online collections. Worldwide coverage, although the United States is an obvious focus.
USGS Map Locator: Access to all scanned and georeferenced editions of USGS topographical maps, current and historical.
NOAA Office of Coast Survey Historical Map & Chart Collection: Historical navigation charts, scanned and georeferenced.
United States National Archives has thousands of maps available with an emphasis on US diplomatic and military history.
The British Library makes a number of collections available online.
Fire Insurance Maps Online (licensed resource): color fire insurance maps, real estate atlases, plat books, and other historical maps showing building structures, building construction details, property ownership, property uses, and other useful information.
ProQuest Sanborn Maps Geo Edition (UNI access): digital access to thousands of large-scale fire insurance maps of US cities, searchable by address and GPS coordinates.
Smithsonian Maps Catalog: The National Museum of Natural History has an online collection of over 30,000 maps.
United Nations Cartographic Section: A number of UN produced general and mission-related maps are available here.
Harvard University Scanned Map Collection has over 2,500 high-resolution historical maps, most of these are also available from Geodata@Columbia.
University of Texas Perry-Castañeda Library Map Collection Online: The UT-Austin Map Library has scanned a large number of public domain maps at varying resolutions. Many of these are government produced maps and includes a number of AMS and CIA sheets.
Central Intelligence Agency (CIA) Maps: Most recent editions of the CIA country maps.