They've been compared a couple times in our group. Cyclades is more cut-throat and has more rules, without really having more depth. I don't mean to say it's a shallow game, it isn't, but it's a little more traditional in it's design. It also tends to be more about warfare. It plays shorter too.
Mare Nostrum is much more of an overall civ game, with trading and so forth. It has more depth, and feels more epic. It's a little tougher to learn though, in terms of strategy.