The Goats are glorious live. Just saw them a few hours ago and it was one of the best gigs I've been to, John's simply amazing. (On an unrelated note, the show had drama too - co-headliner Micah P. Hinson proposed to his girlfriend - she said yes - the crowd went wild - but i digress...)
Picking a Goats album to start on is tricky in my opinion - they all have their strengths and weaknesses. I would probably suggest you go for a different route, head to etree and download one of the live sets to start of with (try the Oct 2004 village tavern one or Feb 2004 earl one), taking it from there. If you have your heart set on an album, the Sunset Tree is probably the one to get, with Tallahassee and All Hail West Texas in tied close second (they probably have more outstanding individual tracks than the Sunset Tree, but less consistancy overall).
As to Will Oldham, I'm much less familiar with but Then the Letting Go (Prince Billy) is a great album (strange form of life being one of the best tracks I've heard in... ever).
Anyways, hope that helps.