I'd imagine any of the standard bigger species would be fine. Glyptoperichthys gibbiceps is a nice catfish, very handsome and usually easy enough to obtain. My Panaque nigrolineatus (still going strong) put up with 7 years with Malawi cichlids. That species is a bit delicate when first imported, but otherwise seems tough as old boots. Liposarcus multiradiatus and L. pardalis are the "common plecs" (in the UK, at least) and though not very pretty are certainly hardy.
In a large cichlid tank a plec will have little to no effect on algae control. It's important to recognise what allows algae to prosper (the lack of plants) and fertilises the algae (the nitrates) in the first place. Adding a plec does nothing about the first issue, and actually makes the second issue worse. "Algae eaters" as sold by many retailers are more about marketing than practical function. You're still going to be scraping off the algae and cleaning the rocks.
http/www.fishforums.net/index.php?showtopic=135919
Since this is the case, you may as well broaden you catfish search for any other species that might be fun, like a large doradid, or a Synodontis.
Cheers,
Neale