There are five levels of difficulty. From easiest to hardest, they are:
Playing on Discoverer is pretty boring, Explorer and Conqueror are good for learning game mechanics, and Governor and Viceroy are for the real fun. Viceroy is a lot easier than Master of Magic's Impossible level, and it should be a comfortable play after a few games.
If you learned the game at lower difficulty, you may be expecting certain things (good quality of immigrants, cheaper founding fathers, low rate of Indian alarm) that don't work that way on higher levels.
Quantitatively confirmed differences
- Size of the King's army
- Number of bells for each founding father
- First Soldier is always a Veteran on Discoverer and Explorer (otherwise only Spanish start with a Veteran Soldier)
- Tutorial hints are turned on by default on Discoverer (but you can change that in game options menu)
Qualitatively confirmed differences
- Indian alarm rate is greater on higher difficulties
- Immigration quality is lower on higher difficulties: fewer specialists, more criminals and servants
Definitely no difference
- Number of bells per population to get revolutionary support
- Strength and speed of armies, production of various goods, cost of buildings, etc. The game's "core mechanics" don't seem to be affected in any way.
- Cost of units in Europe
- Indian treasures, volatility of prices, AI's behavior
- AI's bonuses - but it has difficulty-dependent bonuses in Civ, CivII and MoM, so they're very likely. AI seems to have at least one bonus of free 20 tools and 50 guns in all new colonies, but that may not be difficulty-dependent.