Well you got the right idea with small fish. I will start off by saying I would just leave the barbs out completely. I think they would look funny but I dont know much about keepting them with africans. I believe some Julies can have a bad attitude and are better off in species only tanks, but I have not kept them my self so I am sure someone on here will better know.
In my own opinion I would go with shell dwellers instead of rock dwellers. Things like lamprologus ocellatus, brevis, multifasciatus or any lamprologus species would make a good shellie tank for a 20gal. They usually have a lot of personality as well. Thats just my own opinion.