This is rather a long post....lucky I am not a lawyer who charges by the word.
I got my Sudanese visa in Kampala, Uganda in a couple of weeks for about $US30 (55,000 Ugandan Shillings). I have heard from others that Addis, which is the traditional place to get the visa, has become increasingly difficult and time consuming. Either way, I suggest you email a travel agent in Khartoum two or three weeks before you need the visa, so that they can arrange a letter of introduction and facilitate the process. I used the following guy and he was efficient, although he wanted to charge my US$75 for the privelege (he has never sent me details of the bill or how to pay him, so I have never actually had to pay this - please don't remind him!).
Amr Ali Aljundi
Mafaza Traveling Services
Khartoum 11111, Sudan
I suspect that he can probably arrange for the visa to be collected in any embassy, so you could also do it in Nairobi / Addis if you are not going to Uganda.
No country has really presented any problems for visas on Aussie passports. I have briefly listed the East African countries below and whether you need them in advance or can get on the border.
SA - not necessary
Lesotho - not necessary
Swaziland - not necessary
Mozambique - embassy in SA (although I think South Africans can still get on the border)
Zimbabwe - border US$30
Zambia - free at the border if you get on the list from Jolly Boys backpackers in Livingstone, otherwise US$25
Botswana - not necessary
Malawi - not necessary
Tanzania - US$50 at the border
Kenya - US$50 at the border
Burundi - US$40 at the embassy, although I think it was only US$20 at the Tanzanian border
Rwanda - US$50 at embassy, although possibly available at the border
Uganda - US$30 at the border
Ethiopia - US$20 at embassy, don't know about border
Egypt - US$20 at embassy, don't know about the border
As to hiking, try a Kilimanjaro climb in Tanzania or gorilla trekking in Rwanda / Congo / Uganda. Both of these are expensive activities, otherwise there is good free hiking in most countries, it just depends on your preferences.