Why not allow all Henchmen to start at Level 1 at these places and then be levelled up to whatever advanced level the town has provided? So it would be like the Experienced Sov Profession, except it would apply to Henchman at Fortresses.
Or, at the very least, give one choice of trait for every two levels. So a starting L2 Henchman would get one free trait choice, and a starting L4 Henchman would get two free trait choices. If Stardock considers it too strong to get three levels-up for starting at L4, I think one trait choice for every 2 of starting level, so L2, L4, L6 (if it's possible to get that high) might be acceptable. After all, it is accelerated training that the fortresses do - maybe not hero training.