Yeah, the turtle is really easy with Horsemen, Archmages and a couple of other ranged units. No melee units except for the Horsemen. You can usually get Horsemen from the King's Tent in Greenwort, you just need to get around the strong stack there. Bit of an exploit but it's necessary for this tactic.
To avoid the turtle's footstomp you cast Haste (you need Distortion 2) on the Horsemen, and CHARGE! I think the turtle does the mass slow on turn 1, but that's okay because only the Horsemen will move. You use the Archmage's Magic Shield on the Horsemen, and on subsequent turns you cast Heal on the Horsemen. You can also alternate with Stone Skin to buff the Horsemen even more. The turtle won't do enough damage to kill even one Horseman. Meanwhile you are shooting at the turtle with probably Inquisitors and Archers, and that's it! Using this tactic, I was able to win against the turtle on Impossible on probably day 3. It would work just as well on day 2, it would just take a bit longer due to lower leadership.
The key is you have to use Horsemen to melee the Turtle ASAP. That way the turtle will never do the footstomp, because it will always melee the unit standing in front of it.