You are right on focusing on the strong, bless-effect troops. If you crank out enough Herses early in the game many will get into the Hall of Fame and become quite legendary over time. At first I was using Water 9 for the defense and quickness, but now I think a Great Mother with Earth 4 Nature 9 really maximizes the units' strengths. Those giants have the hitpoints to get their money's worth from regeneration (especially if they're getting hacked up while berserk
and reinvigoration can allow you to get away with Black Steel armor on the commanders (good thing it's one-size-fits-all..) If you can afford it, Earth 9 Nature 9 would be even better and might make those Woodsmen useful for a change. NJ's work great as a prophet - that mass-bless spell is indispensable when you're hauling around umpteen Niefel Giants and Herses. And if you're in a strong dominion he can be a great fighter (with Holy Avenger to boot).
I always get stuck though with Jotun magic - never know what to aim for, and the mages are so expensive (and poor searchers) that I end up falling behind. Should I focus on Blood, or what? And has anyone successfully pulled off an Illwinter? I'm curious to know do the Rimtursar actually ever arrive, or is it just there for the cold and unrest?