This was tested in Free Game mode, settings for Economy and Naval Battles - Very Hard.
Some minor testing was made for Regular difficulty setting, but the differences are not big.

During your gameplay, you will earn Fame and when you fill your Fame bar, you get a Fame Point.
Fame Points are used mainly to unlock concessions, but can also be used to build warships or to gain Administrator rights for a city.

There are 29 total concessions, so you need to gain 29 Fame Points to unlock all.
If you start as a Pirate, you have one concession unlocked from the start (you have one captain).
If you start as a Buccaneer, you are awarded 5 Fame Points from the beginning.

Every time you fill the Fame bar, you get one Fame Point and a new amount of Fame needed to fill the bar is calculated. The first part of that new amount is fixed and the second part is variable.

The Fixed part is increased by 10% each time (starting from 3th Fame Point), usually rounded down by 1 point. In the Regular economy the increase is 5% each time, again usually rounded down by 1 point. You can see the exact numbers below.

Variable part is basically a Trading Penalty, because it is increased by 10 points for every 1000 cargo units (barrels) sold in the last 28 days of game time. The monetary value of cargo makes no difference. Any sales older then 28 days are not considered.

Trading Penalty seems to work the same way regardless of difficulty settings.

The last transaction that gives you enough Fame to level up is not taken into account. If you have sold 999 or less cargo in the last 28 days of game time and then sell 300 Cacao in one click and gain enough Fame to level up, then you are still considered to be below the 1000 cargo limit and the Trading Penalty will be zero.

There seems to be no reasonable cap on the Trading Penalty value - i did the testing on the first Fame Point and with 35000+ cargo sold i got this:
The Trading Penalty value was 350, the fixed amount for second Fame Point is 60 - the result was i needed 410 fame for second Fame Point.


Fixed amounts of Fame needed for each Fame Point (Very Hard economy and Naval Battles):



Fixed amounts of Fame needed for each Fame Point (Regular economy and Naval Battles) - i did the testing for the first 14 points only, but most likely the 5% increase will apply all the way:

Trading:
- sell the required amount of colonial goods in your Viceroy City: +100 Fame per month
- complete Viceroy quests - every 3 months or so - i saw +30-205 Fame depending on task
- complete random city tasks (you need a trading license for the city to see the quests):

• tasks to deliver scarce goods or to buy abundant goods: +20-40 Fame (amount is random)
  
• tasks to order a ship from a shipyard (from Viceroy cities): +20-40 Fame (amount is random)

(the task of unloading workers in the city gives no Fame, best to decline this quest to get new one)

Defeat pirate convoy: +50 Fame (not available in first year or so)

During War - using the Letter of Marque:
- plunder trading convoy: +10 Fame
- defeat military convoy: +25 Fame
- defeat the Treasure Fleet: +50 Fame
- complete the siege of an enemy city: +50 Fame. After that, additionally:

• plunder enemy city: +50 Fame
  
• anex enemy city: +50 Fame

- complete random city task - plunder a specific city or destroy enemy buccaneer: +?? Fame
- complete Viceroy's quest to anex enemy city: +?? Fame

When you start a new Free Game, the set of Game Objectives (short term and long term) is generated randomly. You get one Fame Point for completing each objective. The objectives can be very easy to complete or nearly impossible to complete - it is all luck. You can choose in your Free Game settings if you want military tasks or economy tasks or both (mixed). If you don't like the set of objectives after you created the game, then just make a new one and you may be luckier.

Here is an example of good luck:
This means three very easy Fame Points.

Treasure maps are another way to obtain Fame Points. You need to collect pieces of it first. You can begin to search for the coastal position after you find the central piece of the treasure map. From that coastal location you can then start an expedition, and when it is finished, you will be awarded one Fame Point.

I actually did it in 15 months, but it can be done in less than 12 months for sure.
This was without any Fame Points gained from Game Objectives, all 28 Fame Points came from Fame farming, my starting class was the Pirate.

You can get 1200 Fame in a year from delivering colonial goods.
You can get 100-150 Fame per month from city tasks. That makes it 1200-1800 Fame in a year.
You can get 2500+ Fame from the first war.
This puts you around 5000+ Fame at the end of the first year and that is enough for 25-26 Fame Points.
You can get the remaining 2-4 Fame Points from completing game objectives.

Some tips in this section may be considered as spoilers, so if you want to find out for yourself, how to gain 29 Fame Points in the first year of the game, then stop reading right here.

Many of the following tips are centered around Naval battles, because trading will slow your process of gaining Fame Points.

Funny tip to start with (for a trading game), but Don't trade!
Why? If you keep your sales as low as possible, you can keep the Trading Penalty value at zero until you unlock all concessions. Of course, you have to sell the colonial goods and complete city tasks, but you can still stay below the 1000 cargo limit (see further tips).

Keep the game paused
Why? If you want to be efficient, then you have to. Think about your actions first, write down your sales and their dates, check for new city tasks and check your convoys. Only then unpause, until some new action from you is required.

Starting class - The Pirate and choose Armed Trading Convoys in the game creation
Why? Because you can get rich without trading very fast. The Pirate starts with a warship and a captain, so you can plunder trading convoys right away. Your Fame can't go negative, so at the start of the game there is no penalty for piracy. Don't sell the plundered goods, keep them in warehouse for city tasks or for later, only sell captured ships. Plunder until you have a two-star captain and enough warships to make a four-ship war convoy. Then you can start the delivery of colonial goods and complete the city tasks. Whenever you need gold, sail out with your war convoy, put on the pirate flag and wait until you get attacked by a military convoy - if they start the attack and not you, then you won't loose any Fame. Capture all the ships and sell them to keep you going.

Create a favorable Free Game - keep trying until you get one
Why? Because it can make a huge difference.
And what is favorable?

• Your nation should be as small as possible
  
• One of the colonial goods is produced in your Viceroy City
  
• Get a captain with good perks - Close Combat Fighter is the key perk
  
• Get a game with good objectives, so you can gain 2-4 Fame Points through them

A small nation means that fewer colonial goods are required, and if one of those goods is produced in the city, the required amount is reduced too (for small nations to zero):
The first example is a small nation with cacao produced in Viceroy City and no cities that produce tobacco and coffee. The second example is a big nation with many cities producing coffee. The difference is huge - you get 100 Fame monthly for 509 goods delivered or you get 100 Fame for 5234 goods delivered.

A good captain will help a lot - your main income will be from selling captured ships, so having a captain like this from the start is great:

Put stars in Close Combat Fighter first, then one in Leadership and one in Carpenter - then you have a perfect captain for defeating military convoys and for city sieges.

Get a trading license for several cities
Why? To get more city tasks and to be able to buy required goods, because your small nation will not produce all. Prefer cities close to your nation. The price for trading license will increase with your wealth, so buy them early while they are cheap. The first breakpoint, where the price increases is 95K wealth and the second is 220K wealth. The price change happends on midnight, so if your wealth is bellow 95K at the morning and you manage to capture enemy convoy and anchor in your Viceroy city before midnight, you can then pause the game, sell all unwanted ships and use the gold to buy cheapest trading licenses. Just make sure you don't plunder two trading convoys from same nation - you get away with first one, but after the second, the nation considers you a pirate and the trading license price will be higher.

Prepare for war
Why? Because it is a goldmine for Fame - if you are prepared.
The first war usually begins after 6 or 7 months since the start of the game. Buy the Letter of Marque immidiately. Have a lot of captains and warships and sailors ready - you should spend all your early Fame Points on captain licenses. Plunder every enemy merchant. Lay siege on the closest enemy city and destroy all enemy military convoys, that come for help. Plunder the city after the siege and move to next one. Repeat this as many times as possible. You can lay siege on several cities at once, after you reduced the number of enemy military convoys. You can plunder the same city again after 60 days.

And that is it. I am sorry for all the grammatical mistakes, my English is not as good as it should be. I hope you will find this guide useful and if you discover any errors in it, feel free to comment and i will update the guide.