Altamont Ravenard said:
I want to do something I've never done before, so I've decided to run a high(ish)-level (10-12 to start, I think) game where the players will run evil, "monstrous" (but still humanoid, ie orcs, hobgoblins, bugbears, etc.) pcs. I was thinking of doing some sort of "invasion" scenario, where the pcs are part of a horde that's planning on attacking a civilized region / empire.
This is relatively close to the majority of the games I've run. (We aren't very good at doing Good

paladins never last long either)
First question is what feel do you want to evoke are they going to be powerful but individual forces within the overall horde of darkness or are they leaders? This alone will affect the course of the campaign. If you're going the leader rout the best way to handle it is to make them all leaders of roughly equivalent forces. Give them all
leadership and
extra followers as bonus feats, since they all have them it doesn't present a balance issue. The followers from the feats don't represent their entire command they simply represent their unswervingly loyal inner circle of devoted "household troops." They should have bigger commands overall but these are an undisciplined lot of half-rabid warriors drawn by their power and ability to lead but not truly loyal and at times only barely under control.
Now you need to decide on the overall scope of the horde so that you can set the relative position of the PCs within it. My favorite tactic and one that can be easily scaled is one of the side-thrust, a tendril of a larger horde that has broken off to one side of the main line of advance to pursue their own aims. Remember these hordes aren't modern armies they have no command and control structure. They're just a bunch of independent commands sort of working together.
There won't be more than about three tiers of command regardless of how many are in the horde. This allows bigger fish in the evil landscape to answer to while keeping them distant and allowing the players to shine as leaders of their mini-horde. At any point in time the campaign can be turned to shift the players back into the main horde by manipulating overall strategic level events outside their immediate knowledge. A good way to get the players on their feet at the start of the campaign.
Regardless some things are vital, the other various components of the horde must have memorable leaders. Let the horde itself be a faceless mass but their leaders have to be interesting, as much of the horde campaign lies in interaction with other horde leaders as it does with the enemy. Champions are important, take a note from Homer and make certain that they never just face an actual enemy field force composed entirely of levies. Allow the horde and levies to clash but then bring up the leaders of the forces of Good. Draw them in so that the horde is as much a backdrop as a force of destruction. Plenty of devastating fights in the middle of a crowd of mooks from both sides between the PCs and the Champions of Good.
Dig up every stereotype you can imagine, the first time your orc "warlord" kills a gleaming paladin on a charger after a glorious combat in the Homeric tradition and throws his severed head back into the fallen leader's demoralized human troops routing them your players will cheer. Spread out the fights so that each PC is in their own spotlight simultaneously. While one is threshing through the enemy mooks like wheat another should be reanimating the fallen into an infernal undead legion, another slaying a prominent enemy leader. Magic-users can be more difficult to bring in to this scheme but a good start would be to read some accounts of Civil War(U.S.) artillery duels. Enemy casters on nearby hilltops blasting the

out of each other and the mooks while their own personal guards struggle to hold back close assaults by the enemy infantry.