Although I don't do cichilds personally, a good friend of mine keeps africans in a 110g tank - with MUCH success. He trades at least a dozen surviving babies to the LFS per month. His tank is comprised of sand substate (used to have medium-sized stone bottom before redoing it), and a lot of flat rocks built up to make plenty of caves.
For equipment he has a Magnum 350 canister, the large aquaclear HOB, a powerhead in each rear-corner for circulation, and undergravel jets to keep things from settling out too much.