Hi! I've heard good things about Habari Node[1], and Angania[2] is a startup working on Nairobi-based hosting. That said, I and most developers I know in the region host internationally. As others have mentioned latency is usually a bigger problem than bandwidth. Happy to take a look at your site if helpful (just add it to the form).
Depends on where your clients are in Africa -- if in the South then for example http://www.rsaweb.co.za/ could be a good choice. Have had some VMs with them, no issues.
Do you know of/recommend any local hosts?