Explorers and conquistadors
An explorer can be distinguished from an ordinary naval leader by the "sextant" icon next to his name, which you can see when you select his fleet. Similarly, conquistadors have a "Spanish helmet" icon next to their name.
Conquistadors can enter unexplored land provinces. Moving into unexplored territory takes much longer than normal; see land movement times. Provinces owned by other countries but not known by you can always be explored, without needing a conquistador. You can often identify owned but unexplored provinces by their red border lines, but not always. If you are unsure whether a province is owned, just try sending an army there - if it's unowned, the order won't "take".
Explorers can enter unexplored sea zones. As with land, this takes much longer than normal (see naval movement times; I guess the same 3x time applies). Explorers may also discover land provinces adjacent to any sea zone when they enter it; the chance of this happening not clear. (It may be tied to the aggressiveness of the natives.) Note that leaving a port counts as entering the sea zone; therefore if you happen to have undiscovered lands next to a sea zone that has a port, you can discover them very quickly by looping in and out of that port until the land is revealed.
After you reach land tech 31 you can explore all provinces with any army, although armies with a conquistador still explore much more quickly than those without. After you reach navy tech 18 you will automatically discover all land provinces which any of your fleets sails by. When you reach navy tech 27, you can explore sea zones with all navies.
Explorers and conquistadors are extra effective at reducing attrition. Most explorers and conquistadors have higher maneuver values than default leaders. Conquistadors augment supply by 4*maneuver (compared to 2*maneuver for other land leaders); explorers reduce effective time at sea by 2*maneuver (other admirals: 1*maneuver). In addition to this, an army/navy commanded by a conquistador/explorer does not suffer from movement attrition.
An explorer or conquistador will increase colonization chances (and lower costs), if one of them is in a province (even if it is moving) at the moment when you send a colonist there. (Note that in order to be in a land province, an explorer must be in a port; so explorers can never help out with the initial colonization of a province.) The chance to colonize is increased by five times the maneuver number. However, only the best bonus from among all explorers/conquistadors in the province will apply. Colonization chances are capped at 95%. However, even after you have reached 95%, a conquistador or explorer will lower the cost to colonize. The colonization benefits are the primary use for explorers and conquistadors in the later game, when you've explored everything.
Finally, conquistadors are superior to normal land leaders in dealing with natives. Supposedly they are more effective against natives in combat. They also are much less likely to trigger a battle against natives when entering a province. (I don't know of any numerical quantification of either effect; please edit if you know anything.)
On the negative side, conquistadors have their fire, shock and siege stats nullified if they are in Europe. For example, a conquistador with the stats of 3/3/3/1 has the stats 3/0/0/0 in Europe.
Certain countries will get explorers as historical leaders. Historical leaders of all kinds are generated on a fixed date (the same date in every game). Countries which get at least one historical explorer are: Portugal, Spain, Holland, England, France, Denmark, Flanders, Russia, and China. Additionally, Brandenburg, England, Austria, and Japan may receive scripted random explorers; some of these events are conditional, however.
Year Name of Event Preconditions* 1550- Explorer land<=3; naval>=11; trade>=3 1550- Explorer land<=1; naval>=11; trade>=3 1600- Explorer land<=3; naval>=18; trade>=5; mercantilism<=3 1600- Explorer land<=1; naval>=18; trade>=5; mercantilism<=1 * "land" here is the domestic policy slider, not land tech.
As with explorers, certain countries also get conquistadors as historical leaders. Countries which get at least one historical conquistador are: Spain, Portugal, England, France, Denmark, Holland, Poland, Sweden, Russia, Ottomans, Flanders, Morocco, Iroquois, and Dai Viet. Additionally, a scripted random conquistador will be given to Portugal, and one may be given to France.
All countries can get conquistadors through random events. There are three random events that can give you a conquistador:
Year Name of Event Preconditions 1500- Conquistador none 1550- Colonial Dynamism none 1600- Colonial Dynamism innovative <= 3