Compared to the countries in West Africa to get visa for East African countries is quite easy. For most countries you can get the visa at the border: Botswana, Zambia, Zimbabwe, Mozambique, Malawi, Tanzania, Uganda, Kenya. There are some exceptions.
RWANDA. According to fellow-travelers the visa for Rwanda has to be applied at the embassy in Tanzania but I got the Rwandese visa simply at the border. For Belgian travellers it seems to be difficult to get a visa for Rwanda.
ETHIOPIA. Travelling from south to north the only place to apply for the Ethiopian visa is at the embassy in Harare, Zimbabwe. My visa was issued the same day and without any hassle. The Ethiopian embassies in Kampala and Nairobi don't issue visa anymore! Travelling from north to south a visa can be applied in Khartoum. There are problems regarding the usage of the Carnet de Passage. Travelling from north to south, from Sudan to Ethiopia, the carnet is not accepted. You need a letter of guarantee from your embassy in Addis Abeba. Travelling from south to north the carnet is accepted and I didn't need a letter of guarantee. This regulation was introduced suddenly in may or june 2010.
SUDAN. I got the visa for Sudan from the embassy in Nairobi, Kenya. A letter of recommendation of your embassy is demanded but I got the visa without a letter. Visa was issued the next day after appliance. If travelling from north to south apply in Cairo.
EGYPT. I got the visa from the Egyptian embassy in Khartoum. However visa were issued too on the ferryboat from Wadi Halfa to Aswan.
Visa cost generally about 50 to 60 US dollar. You facilitate your appliance if you are dressed decendly: no short trousers, no blue jeans, no sandals, no t-shirt, shaved. When I applied for a visa at the Sudanese embassy in Nairobi a British couple was denied, probably because they were dressed in short trousers and sandals. The Gabonese embassy in Yaounde, Cameroon, refused two Chinese because they were dressed in blue jeans (black jeans were no problem).
Have a good trip.