He'll be level 12 to match the region, so plan according to that. The type of lieutenant it turns out to be will have some substantial effect on the difficulty of it, too; you can always brave his keep, get to him, and then see if he seems overwhelming -- if so, run for the exit and then warp out to the edge of the region from the next room. You can then come back in just a single warp potion once you're ready to tackle him, and at that point you'd have much better intel on specifically why this guy was hard and what would best be usable to kill him, etc.
In a very real sense, the best time to take on a lieutenant is a personal question that is based on your own skill and playstyle. If you're really awesome at dodging attacks and landing tricky hits with a variety of spells, then you can probably take him early. If you're relying more on planning and properly outfitting, and/or even on overleveling the opponent, then you'd want to level up more before taking him on. The game is really meant to be able to cater to both action-oriented players and more thoughtful planning-oriented players. When it comes to this game, I'm the former and Keith is the latter, so we'd both have completely different answers on how to deal with something like this.
Hope that helps -- I imagine other players can weigh in, too!
