United States Census Bureau - http://www.census.gov/ 
more recently the 2010 census - http://2010.census.gov/2010census/

FedStats - http://www.fedstats.gov/

Google Public Data - http://www.google.com/publicdata/directory (follow links on site to find the actual original data set)

UCI Knowledge Discovery in Databases Archive - http://kdd.ics.uci.edu/

The World Bank - http://data.worldbank.org/

Infochimps - http://www.infochimps.com/datasets

Large list of dataset sources - http://kevinchai.net/datasets

Musicbrainz Music Metadata - http://musicbrainz.org/

Public Data Sets on AWS - http://aws.amazon.com/publicdatasets/

Canada Open Data - http://www.data.gc.ca/default.asp?lang=En&n=F9B7A1E3-1

Data.gov.uk - http://data.gov.uk/

DataMarket - http://datamarket.com/ - requires signup, but has 30 day free trial

CESSDA - http://www.cessda.org/

DataMob - http://datamob.org/

DataSF (san francisco) - http://datasf.org/

California Data - http://www.cde.ca.gov/ds/fd/fd/

IMF (international monetary fund) - http://www.imf.org/external/data.htm

Financial Data Finder - http://fisher.osu.edu/cgi-bin/DB_Search/db_search.cgi?setup_file=finance.setup.cgi

Gene Expression Omnibus - http://www.ncbi.nlm.nih.gov/geo/

Google Books Ngram Viewer - http://ngrams.googlelabs.com/datasets

MLData - http://mldata.org/

NASA Planetary Data - http://pds.jpl.nasa.gov/

NASA Space Physics Data - http://spdf.gsfc.nasa.gov/

PubGene Data - http://www.pubgene.org/

Time Series Data Library - http://robjhyndman.com/TSDL/

Wikipedia User Contribution Dataset - http://nile.ics.uci.edu/events-dataset-api/

Wikiposit - http://wikiposit.org/

Corporate finance data - http://people.stern.nyu.edu/adamodar/New_Home_Page/data.html

Yet more finance data - http://fisher.osu.edu/fin/osudown.htm

Macroecon data - http://fmwww.bc.edu/ec-p/data/ecfindata.php