Agents are the way the Forces of Justice will attempt to stop or disrupt your evil deeds. There are various different types of them, each with different goals.
Agents will also appear on the World Domination map from time to time, causing periodic casualties amongst Stealing or Plotting minions, and causing more casualties during Acts of Infamy. Super Agents (as later described) when present on the World Domination map are even more effective at this.
Virtually all agents on your island belong to a particular alliance and will accumulate heat pieces (marked by red quarter-rings around their selection circle) when they come across anything iffy like a body bag, or are attacked for any reason. Your appropriate alliances' heat will rise if they then leave the island with that information; either use the Weaken tag to make them forget what they've seen, or dispatch them.
As your heat with a particular alliance rises, they will tend to send more of more dangerous agent types.
Investigators and Agents
These guys are usually not very much of a threat. They don't have any purpose other than to gather incriminating evidence, aren't very good in combat, and are generally poor at base infiltration. Agents are marginally-better Investigators, appearing in greater numbers and having more health and firepower.
Burglars and Thieves
Again, more of an annoyance than anything else, these guys will seek to steal any of your ill-gotten assets ranging from briefcases to gold to any loot items. Be wary that you will lose notoriety if loot stolen by these guys makes it off the island, so when you hear the "Object Stolen!" voice alert, find the offending character and tag them for termination or capture to make them drop what they're carrying. Thieves are to Burglars as Agents are to Investigators; marginally more health, firepower, and infiltration ability.
Infiltrators and Saboteurs
Very dangerous if they're allowed too far into your base; they will find anything with a modicum of heat and destroy it, from sentry guns to power generators. Failing that, they will just go for your traps. It can be annoying if they keep destroying stuff around your base entrance(s), but quick elimination backed up by a healthy supply of Technician and Valet minions with fire extinguishers will mitigate most of the damage. Bear in mind also that these guys are also quite tough and in numbers pose serious threats to lone Henchmen.
Soldiers and Veterans
The heavy-hitters; these guys function like Infiltrators and Saboteurs in that they will destroy your base, except these guys will do it from the outside-in rather than inside-out, and they're wielding a lot more firepower. Single henchmen won't stand a chance against groups of these if they're anything higher than Poor, unless you can even the odds or have special abilities at the ready (Red Ivan's bazooka can help, or Jubei's Evisceration). If these guys get too close, up the alert level and let your swathes of minions take care of them. Fortunately however, these guys are more likely to trigger your traps compared with Infiltrators. Also be wary that Soldiers and Veterans will start berserking if they are either attacked or accumulate too much heat, attacking absolutely everything and anything on your side that they see including non-hostile minions.
The deadliest enemies of all, but fortunately there's only 5 of them, and they're triggered by Notoriety rather than heat. Super Agents are invincible under normal circumstances; they cannot be permanently killed. Depleting their health to 0 will function the same as if your henchmen's health gets depleted to 0; they will just fall over, stunned, for a short while, before getting back up. Super Agents wield the highest firepower of all enemies, often capable of killing minions in single hits, and even have special abilities. Each territory has a Super Agent.
But be warned about sending your henchmen to fight Super Agents; if they land a "killing" blow, then that henchmen will lose a life. They have three, and they're gone for good if they lose all three (unless you use the console to bring them back).
Whereas Super Agents cannot be killed in normal combat, they do all (with the slight exception of John Steele) have a secret weakness, which you will receive Optional Objectives during your time on the second island that will hint towards what that weakness might be. Of course, it's listed here for your convenience.
S.M.A.S.H. - Mariana Mamba
Mariana Mamba begins appearing at notoriety level 140 and behaves like a saboteur and a thief. Her special ability is called Savage Allure, and if it used on a minion, it sucks away practically all of their loyalty! She won't last long in a melee fight though, and has no ranged attacks. Plus, Savage Allure will render her immobile for a few seconds. To permanently stop her, you'll have to complete Optional Objective 4, wherein you turn her obese, therefore nullifying her main weapon; her looks.
A.N.V.I.L. - Jet Chan
H.A.M.M.E.R. - Katerina Frostonova
P.A.T.R.I.O.T. - Dirk Masters
S.A.B.R.E. - John Steele
The nastiest of all the Secret Agents, John Steele only appears at notoriety level 340 and behaves like both a saboteur and investigator. His special ability, Base Mayhem, can... well, wreak mayhem on your base. Not only does it reset security levels on the doors and potentially mess with your base's alert level, it causes explosions everywhere! Worse still, there's no objective for removing him, meaning that you can't get rid of him! However, if you set off your Doomsday Device on Objective X and you have him in a holding cell, you'll get treated to a cutscene showing Steele being blasted off with your rocket into oblivion.