Texture Databases
Link to original thread at TWC
Mayang's Free Textures
If you cant find what you need here, then stop looking. It's not on the internet.
Textures and Backgrounds Not a huge selection, but well organized
LOTR Textures Some very different types of textures you may not find elsewhere
Seamless Texture Library Posted by Caius Britannicus - Currently Down
Stone Textures Stone textures broken up into specific categories (i.e. Sandstone, Granite, etc)
Stockvault Moderately large 'vault' of well organized textures
m3corp Posted by vikrant1986. Boasts 3d textures as well as tutorial on how to make them.
MetalCity Easily browseable thumbnails dividing by category
If you know of any other good websites that host textures, please post here and they will be promptly added to the list. Thanks.