Sweet! So level 2 should be plenty enough for a start.They changed the skill system some patches ago. I haven't tried it so take everything I say with a grain of salt, but it seems you don't need to level up men-at-arms at a high level to get the more powerful skills, but let you have new active skills.
For example, men-at-arms level 1 let you have 3 warrior skills, level two adds... 2 more? and so on. You can unlearn your skills freely, but you need a skill book to learn it again. I think high level men-at-arms make you skills cost less AP and have shorter CD, but again, I haven't tried the new system, so I'm not sure.
EDIT: From the changelog that changed that:
EDIT 2: ForkTong, one of the developers, explains the change and why they did it: http://www.larian.com/forums/ubbthreads.php?ubb=showflat&Number=495329#Post495329 and http://www.larian.com/forums/ubbthreads.php?ubb=showflat&Number=498474#Post498474
And yeah,max level yields +4AP and -1 round CD for warrior skills afaik.