The campaign starts simply enough, with the standard "giant hoard of savage humanoids appears out of nowhere and there is a great wrecking of shit" scenario. The complication is that the orcs, goblins, gnolls, hobgoblins, bugbears, lizardfolk, etc. that make up this hoard all have 10-15 character levels each, so their army - which, unlike most such armies, runs like a well oiled machine - is pretty much unstoppable, given that the average NPC soldier is only lvl 2 or 3. On top of that, they have giant war beasts the size of small castles that they use as living siege engines, so the situation for the world looks bleak. The first part of the campaign is surviving the onslaught and trying to figure out where the hell these guys came from. After that, there are several different courses of action that could be taken, but eventually you'll have to take down one of their four generals. Which one you go after and how you plan to kill him are, of course, up to you.
In the process of this, you will naturally have to travel to exotic locations and meet some rather interesting people. Given that you guys wanted this to be an evil campaign, you would start out just trying to survive, but eventually you could try and take control of some part of the enemy army, with which to carve out a kingdom of your own.