At the beginning of the plot phase Player A has 4 cards in his hand and Player B has 3 cards in his hand. Player A reveals Rule by Decree plot card:

Cannot be cancelled. When revealed, the player with the most cards in hand chooses and discards cards from his hand until he has 4 cards in hand.

...and Player B reveals Building Season plot card:

When revealed, choose an opponent. Then, you and that opponent must each search your decks for a location, reveal it, and put it into your hands. Then, shuffle your decks.

Question: Which player's plot card is considered first? Because here - if Player's A, then Rule by Decree does not do anything, but if Player's B, then both players get +1 card and now Player A has to choose and discard one of cards in his hand because of Rule by Decree.

ed00011 said:

The first player determines the order in which all "when revealed" plot effects are resolved.

Thank You, but one more question then: Am I correct that The First Player is determined randomly before the game begins and in the particular example above The First Player is the player who had been chosen to be The First Player by the player who won initiative in the previous round?

No. If you look at FAQ, page 18, plot phase flowchart, you'll see:

1. Choose and reveal plots
2. Initiative is counted
3. High initiative player appoints “First Player”
4. "When revealed" plot effects resolve (In order determined by First Player)

Said another way, the First Player in your Building Season/Rule by Decree example will be the player selected to be First Player by the player who won the initiative count that you should have had immediately upon revealing Building Season and Rule by Decree. (Or, barring other initiative modifiers, the player who revealed Rule by Decree. 4 > 1.)