Cocobear, around the city I can't think of anything right now, but I will look for you. But, if you and your DH like driving, you have two places that you can go.
One is the Chapada dos Veadeiros where you can camp and hike. Here is a website, in English, where you can find some info: www.chapada.com.
Another place I think you would enjoy is Pirenopolis. Unfortunatly, I just found a website on wikipedia in English, en.wikipedia.org/wiki/Piren%C3%B3polis. The other ones are in Portuguese: www.pirenopolis.com.br/ and www.pirenopolis.tur.br/portal/index.php.
They are 4 and 2 hours drive from Brasilia and, maybe, you just need to take a yellow fever shot and also be careful with snakes.
Can I get your e-mail address with Albert? This way I can send more info on this.
Albert, too late... Already addicted!