Cichlids sound awesome. The beauty of fish keeping is experimenting and creating an ecosystem that you like best.
Due to the seasonal changes in NJ, I keep my Koi with Shubunkin and some Comets and have added a tri banded hi fin banded shark to clean up the algae.
I tossed in some blue shubukins to broaden the coloration of the pond.
I would not suggest placing fancies (like moors or butterflies in the pond). During mating season, the koi really beat up the female goldfish and lesson learned.
Whatever you do, compliment with Plants and enjoy for years to come as you plan out your next pond that will be twice the size of this one!