Im a huge fan of the sydontis eupterus. They hold up well in cichlid tanks, can hold their own in a fight and are drop dead gorgeous to boot. As for cleaning they like anything meaty. excess cichlid pellets will work, and shrimp pellets to supplement.
Another choice I love if you can find them, and this is a huge if. Ive only ever seen 2 healthy specimens in my area large enough to put in my tank and I quickly bought both, well I traded a 14" clown knife for one. The species is sun catfish or eclipse catfish, or spot catfish. Whatever they call em. They are just gorgeous and have a wonderful personality rivalling that of most cichlids. They grow quickly and can definitely hold their own.