The Library of Canada has an amazing site called the Virtual Gramophone. This is supposed to be primarily Canadian content, but many of them seem to be US and French recordings which were released in Canada. The recordings range in date from the beginning of the 20th Century up until the 1940s. The French stuff seems to run later. Perhaps French copyright laws aren't as insane as those in the US.
http://www.collectionscanada.ca/gramophone/index-e.html

One of my favorite sites is "Hot Dance". A guy name Glen Richards inherited a large private collection of '78s from the '20s and 30s, and has been gradaully converting them to MP3s and offering them for free on his website. These are a eclectic mix of big name bands like Benny Goodman or Jimmy Lunceford and some pretty obscure and long forgotten groups.

It is a good idea to get on his email list so you know when he has loaded new offerings. He doesn't keep them up there forever, so I would advise downloading them as soon as they are available.
http://www.2multiples.com/hotdance/

For really early stuff, there is "tinfoil.com". This is primarily devoted to late 19th and early 20th Century wax cylinder recordings. Most are in "Real Audio" format, so they aren't intended to be copied (that doesn't mean they can't be--but I am not advocating such behavior on this website).
http://tinfoil.com/

Also in Real Audio format, but focusing on the '20s and '30s is "Radio Dismuke". It is also available as web radio or on iTunes.
http://www.dismuke.org/radio/

A similar service is offered by the "Red Hot Jazz Archive", which has information on thousands of bands as well as many, many recordings. http://www.redhotjazz.com/

The Library of Congress has an interesting assortment of offerings. Click on "Performing Arts: Music" for online music, sheet music and other content: http://memory.loc.gov/ammem/index.html

First World War.com http://www.firstworldwar.com/audio/

Jack Hylton Recordings: Jack was one of the biggest British bandleaders of the '20s-'40s, and here are Real Audio files of most of his stuff http://www.petefaint.co.uk/jackhylton/music.htm

If you have other suggestions, please add them as "Comments". Please note that this post is about free sources for vintage recordings. Hold your suggestions for great places to buy stuff or cool retro bands that are doing good stuff right now, for future posts.