I ended up going with the pool filter sand, as the shop gave me a bag free. I've moved the intakes for the filters so theyre as close to the top of the tank as possible (its 18" deep) and so far so good, the sand is pretyt heavy and I havent had a problem with it getting stirred up. You only need a thin layer (about 1") and most fo the muck/poo/etc sits on top of it, so its easy to clean, I just give it a quick syphon every 3-4 days.
As for the sand being bad for their digestive systems, from that I've heard most ca and sa cichlids encounter sand in their natural habitat, and no one I know of who uses sand has had any problems.