Spellcasters with short-ranged, but damaging spells are pretty good candidates, as they can theoretically also cast spells first turn. If you go first, you might struggle actually getting them behind enemy lines without running though. Efreet are probably the best of these, but alchemist curse is also very good.
Spellcasters can be hunted down by the cheap combat heroes that many armies bring though.
Combat characters and road-block characters are also pretty good. Blaine can be taken by anyone and bring his own inspiring and he can shoot the first turn. Rhordin can survive a long time behind enemy lines and probably be a pain in the ass. Of course, there are lots of weaknesses with being a slow infantry character. It is fairly easy to run away from you, it is easy to catch them if you have combat characters of your own etc.
Overall, teleport is a great spell, but for many armies, still pretty situational. Brock lords are still waaaay better than teleporting Orlaf