Don't know if you've heard of these, but all are pretty good and all are about as far back as these things go:
"The American Old West / Woodward's Reminiscences" by General THomas S Woodward. I know the whole thing is online somewhere...
Albert James Pickett: "HISTORY OF ALABAMA" Also online in full, somewhere.
"The Collected Works of Benjamin Hawkins, 1796-1810" which is online too, at books.google.com at least.
The one mentioned earlier, "History of the Indian Tribes of North America," By Thomas McKenney, 1872: http://www.accessgenealogy.com/native/history_indian_tribes_...
and also the US G'ment papers that are online:http://rs6.loc.gov/ammem/amlaw/lwsp.html
(use the search)http://wardepartmentpapers.org/document.php?id=8244
These are great, but require a LOT of reading to find tidbits. The first one are scanned, typeet (long ago) and indexed, but the second one also has links to the handwritten originals.
The nice thing about online vs. written is the indexing.