Where can you download DEMs?

Unfortunately, there is no one source because DEMs come in many flavors and for many areas.

Geographic Resources

Alexandria Digital Library Gazetteer. This is the first stop for finding the position of anything on the planet.
http://middleware.alexandria.ucsb.edu/client/gaz/adl/index.jsp

GNIS Query Form. The USGS has a handy query form to help you find all things geographic (USA).
http://geonames.usgs.gov/pls/gnispublic

Surface Distances between Points of Lat/Long
http://www.vsv.slu.se/johnb/java/lat-long.htm

Explanation of Circle Distances
http://www.fes.uwaterloo.ca/crs/geog165/gcoords.htm

Great Circles with Waypoints
http://www.info.gov.hk/mardep/javascpt/gcsail.htm

World

NGA GEOnet Names Server. A resource for searching non-US geographic names.
http://earth-info.nga.mil/gns/html/index.html

GTOPO30 files (~10 Mb compressed) are available for the world in 40 deg lon x 50 deg lat tiles that must be gunzipped and untarred into a 57.6 Mb DEM.
Resolution: approximately 1 kilometer.
Source: http://edcwww.cr.usgs.gov/landdaac/gtopo30/gtopo30.html
Alternate source: I have CDs of the compressed files and WCS 5 project file. Contact me for costs.
Cost: none
Copyright Restrictions: none
How-to with WCS

ETOPO5 files that include continental and oceanic terrain.
Resolution: approximately 5(?) kilometers.
Source: http://www.ngdc.noaa.gov/mgg/global/global.html
Cost: none
Copyright Restrictions: none

Combined GTOPO30 and ETOPO5 files cleaned and integrated by David Sandwell at Scripps. Subject to some copyright restrictions.
Resolution: approximately 3 kilometers.
Source: http://topex.ucsd.edu/marine_topo/mar_topo.html
Cost: none
Copyright Restrictions: see site

SRTM HGT files in 1º x 1º blocks
Information: http://www2.jpl.nasa.gov/srtm/cbanddataproducts.html
Source: ftp://e0srp01u.ecs.nasa.gov/srtm/
Cost: none
Copyright Restrictions: none

ASTER Global DEM (GDEM) data was released in 2009 and offers 30-m terrain data for most of the planet. Whether the data is actually 30-m resolution remains to be seen. Note the limitations on use.
ASTER GDEM site (Japan)
NASA WIST site
Review at ViewfinderPanoramas.org

Landsat images aren't DEMs but are very useful
USGS Archive: http://glovis.usgs.gov or http://earthexplorer.usgs.gov
University of Maryland Global Land Cover Facility: http://glcf.umiacs.umd.edu/index.shtml

Bathymetry
Global Multi-Resolution Topography (GMRT)

United States

Query Form. The USGS has a handy query form to help you find all things geographic.
http://geonames.usgs.gov/pls/gnispublic

1:250 000 scale, 1 deg lat x 1 deg lon tiles (~10 Mb compressed).
Resolution: approximately 90 m
Source: http://edcwww.cr.usgs.gov/glis/hyper/guide/1_dgr_demfig/index1m.html
Cost: none
Copyright Restrictions: none

1:24 000 scale DEMs previously on the USGS site have been moved to the GISDataDepot. The DEMs are now organized by state and county. The new SDTS files cannot be imported into WCS v5.52 and earlier versions; v5.53 and later versions can import them. 10-m DEMs are also available for some areas. Equivalent to 7.5-minute and 15-minute USGS topo maps. Best resolution.
Resolution: approximately 30 meters, some 10-m data available
Source: http://www.gisdatadepot.com/dem/demdownload.html
Cost: none
Copyright Restrictions: none
How-to with WCS

USGS National Elevation Dataset (NED) at 1:24,000 (1:63,360 Alaska) scale
http://seamless.usgs.gov/

Bathymetry
National Ocean Service's (NOS) Estuarine Bathymetry
Hawai'i: Coastal Geology Group
Washington: USGS

Canada

GeoBase. Lots of government agencies came together to make quality GIS data available.
Resolution: 1:250K and 1:50K DEMs, coverage varies
Source: http://geobase.ca
Cost: no
Copyright Restrictions: see site

Canada Digital Topographic Data. Subscription agreement for download of National Topographic Data Base (NTDB), the Canadian Digital Elevation Data (CDED), the new Updated Road Network (URN) product and the Administrative Boundaries.
Resolution: varies
Source: http://www.cits.rncan.gc.ca/siteCITS/servlet/CITS?site_id=01&sessionid=&page_id=1-006
Cost: yes
Copyright Restrictions: see site

United Kingdom

Britian's Ordnance Survey Maps
Source: http://www.ordsvy.gov.uk/
Cost: yes
Copyright Restrictions: see site

Northern Ireland's Ordnance Survey Maps
Source: http://www.osni.gov.uk/
Cost: yes
Copyright Restrictions: see site

Not of this World

Moon
Source: http://webgis.wr.usgs.gov/pigwad/down/moon_dl.htm
Cost: none
Copyright Restrictions: none

Mars
Source: ftp://ltpftp.gsfc.nasa.gov/pub/projects/tharsis/MOLA/GRIDS/
Cost: none
Copyright Restrictions: none
Mars a 'la MOLA tutorial for WCS
Mars a 'la MOLA tutorial for VNS

Source: ftp://pdsimage.wr.usgs.gov/cdroms/vo_2007
Cost: none
Copyright Restrictions: none

Venus
Source: http://delcano.mit.edu/mgn/DATA/
Cost: none
Copyright Restrictions: none

Other Data Resources

Guide to data sources...: http://web.port.ac.uk/departments/sees/staff/whitworth/pdf/datasources.pdf
Geodesy for the Layman, among other things NIMA: http://www.nima.mil/GandG/pubs.html
Landsat 7 Facts: http://geo.arc.nasa.gov/sge/landsat/l7.html