Maybe I should explore playing fighters that do not specialize in a weapon. My barbarians did well so far but they compensated for it with rage and being able to use a plethora of different weapons. Nevertheless, I still think a NPC fighter 4 needs the specialization to compete with the PCs in damage output. It would shurely be very 'realistic' to fight an inefficient fighter who plans on becoming level 6 to get an early whirlwind attack, OTOH I do not think his CR would be up to par with a cleaving and specialized fighter.
~Marimmar