1. Considering redesigning the character some more. It's not that it's not okay, but it's more like, we already have a CA-type game with graphics of sort of that style (Terraria). I'd like to distance this game as much as possible from that.
2. Abandoning the "coordinate list" more of keeping track of updates. The sort is just too much of a performance penalty. Someone MeMailed me a while back and suggested using a quad tree to keep track of which cells needed to be updated, but I frankly don't see how I would get substantial advantage from that. I will admit I am no expert on the structure though. It seems to me that any advantage gained from that wouldn't be greater than just iterating through them and using update flags to rapidly skip by any cells that don't need calculation.