The thoughest battles I had were against Dark Hunters. I once entered a battle with a small army of 30 good units(vaegir veterans, horsemans and knigths) and, even though I won, I lost the whole army (only me, Borcha and Marnid survived). Those black khergit seen strong too, but I never had much trouble destroying then.
Those deserters are usually difficult too, specially de swadian ones. Never worried too much about bandits, they usually are easy to kill. But I guess that, among the bandit kinds (river pirates, forest and mountain bandits, sea raiders) mountain bandits are the hardest cause they are always in large numbers. Those "troublesome bandits" from the guests can be a bit hard too, since thay are also in large packs and are better equiped than most of the bandits.