the leviathan is kind of overpowered, with 32 hp who needs submerge? only threat might be freeze, or grav pull if they have creatures out, eternity could also devastate as well, but its only real drawback is its cost, which can easily be payed (late-mid game) unless you have ice drags (unlikely). also the roc is kind of just a lesser version that can be hit by RoF and spells. the lower cost has its benifits but isn't usually worth it in the long term.
perhaps a creature like "dust devil" or whirlwind or something. dunno what the ability should be, but it shouldn't be the same.
I really love all the other ideas, especially the cyclops, suck it otyugh indeed