You can try java ferns and be pretty much guaranteed success - they're bitter (in fact mildy toxic) and won't be chowed down. You can just plug them into crevices and they will take nicely to the rockwork. Vallis, in my experience, will be continually ate. Onion Plants (Crinium) will look great planted in substrate - in your size tank I'd put maybe two at the back in one corner and one in the other at the back again and they will grow up and accross the water level and give nice depth and break up vertical line of sight between the fish - which helps prevent excessive aggression.
Bottom dwellers - synodontis catfish are best for african tanks. Multipunctatus are, in my opinion, the most handsome of the lot