One other suggestion (they are going to attack me on this), I think you could do a couple of yellow Labidochromis and a couple of Ahli in a 25. I have seen people do it in less. Just pile the rocks up high with a number of caves, and get the best filtration you can.
Substrate could be crushed coral.
The fish aren't terribly aggressive (at least the least aggressive African Cichlids I know of aside from the shell dwellers and some of the gentle giants...)