Higher-Level Grunts
Once the PCs start going up levels, the common-or-garden grunt loses its appeal, no matter what combination of weapons it uses. In order for it to become a challenge in proportion to the character's abilities, they need to gain some levels too. It's a pretty safe bet that the more powerful employees can afford better equipment. Even if you don't want to dole out magic to the rank and file, equipping soldiers with breastplates, composite longbows, masterwork weapons and shields and special items (alchemist's fire, acid, tanglefoot bags, thunderstones, etc) can go a long way.
Encounters with grunts can be varied too - since soldiers are divided up into groups, they need leadership from someone ranking below the evil mastermind. Depending on the level of detail you want in your adventure, the stats for any soldier ranking below an officer can easily be reused time and again. Although prestige and position can be determined by things other than character level, as far as the grunt is concerned, skill at fighting equals rank. Try the following on for size:
Mêlée Corporal, male human War2: CR 1; Medium Humanoid (Human); HD 2d8+3; hp 12; Init +1 (Dex); Spd 30 ft.; AC 16 (+1 Dex, +3 armour, +2 shield), touch 11, flat-footed 15; Base Atk +2; Grp +3; Atk +3 melee (1d8+1/19-20, longsword) or +3 ranged (1d6+1, javelin); Full Atk +3 melee (1d8+1/19-20, longsword) or +3 ranged (1d6+1, javelin); Space/Reach 5 ft./5 ft.; AL LE; SV Fort +3, Ref +1, Will -1; Str 13, Dex 12, Con 11, Int 10, Wis 9, Cha 8.
Languages: Common.
Skills and Feats: Climb +3, Intimidate +4, Jump +3, Listen +1, Spot +1; Alertness, Toughness.
Possessions: Longsword, dagger, studded leather, heavy wooden shield, 2 flasks of acid, alchemist's fire.
Total Equipment Cost: 89 gp.
The corporal acts as a squad leader. Normally you'll get one corporal for every ten grunts. If the squad is divided up into smaller patrols of five or so, you may get a lance-corporal too. Strictly speaking, this is a normal grunt with the responsibilities of the corporal, but who draws the pay of a regular guard. At your discretion you may wish to equip the lance-corporal with a corporal's equipment too.
Mêlée Sergeant, male human War3: CR 2; Medium Humanoid (Human); HD 3d8+3; hp 16; Init +1 (Dex); Spd 30 ft.; AC 17 (+1 Dex, +4 armour, +2 shield), touch 11, flat-footed 16; Base Atk +3; Grp +4; Atk +5 melee (1d8+1/19-20, longsword) or +4 ranged (1d6+1, javelin); Full Atk +5 melee (1d8+1/19-20, longsword) or +4 ranged (1d6+1, javelin); Space/Reach 5 ft./5 ft.; AL LE; SV Fort +3, Ref +2, Will +0; Str 13, Dex 12, Con 11, Int 10, Wis 9, Cha 8.
Languages: Common.
Skills and Feats: Climb +3, Intimidate +4, Jump +3, Listen +1, Spot +1; Alertness, Toughness, Weapon Focus (longsword).
Possessions: Longsword, dagger, chain shirt, heavy wooden shield, acid, alchemist's fire, tanglefoot bag.
Total Equipment Cost: 154 gp.
The corporals report to a sergeant - there is usually one of these per platoon, overseeing the actions of the squads. Sergeants are promoted on the basis of their leadership qualities, length of service, combat experience and valour in battle. The platoon cannot operate properly without a sergeant. Although the officer (usually a lieutenant) is the leader and gives the orders, it is the sergeant who ensures that they are carried out properly, provides an insight into the strengths and weaknesses of the platoon and supplies the officer with much-needed experience. The officer ignores the sergeant at his peril!
Officers
Officers are, for the most part, a different kettle of fish from the grunts. Each officer is in charge of 30 or more soldiers, and has a different background and duties from the rest of the grunts. They have to report to their commanding officers, and see to the administration of their platoon, company or regiment. The most powerful officers ought to be generated as an NPC in his or her own right, although in larger campaigns standardised statblocks for lieutenants, captains and so forth can save a lot of work.