They take damage from both fireballs

The key for me is the word "effects" from your quote:

The effects of the same spell cast multiple times...

I would argue that the damage dealt from the fireball is not an "effect" in the context of what your quote is talking about. This spell simply deals damage and has no additional "effects".

Furthermore (as pointed out by @PJRZ), the section you quote from begins with this sentence:

The effects of different spells add together while the durations of those spells overlap. (PHB, pg. 205)

This suggests that spells that simply have an instantaneous effect do not come under this rule, this they effectively have no durations. This also confirms that the context I mention above is for ongoing effects of a spell, where considering overlapping bonuses or additional effects makes more sense.

Instantaneous isn't a real duration, it's just a category of duration for the purposes of that property of a spell

Instantaneous means it has no duration; as for the duration of a spell being listed as instantaneous, I understand duration in this context to simply mean the name of a category, a property of the spell, but it isn't actually a "duration" unless a number is given (or "Until dispelled"); i.e. until a period of time passes to make "duration" meaningful.

From PHB, pg. 203:

Duration

A spell's duration is the length of time the spell persists. A duration can be expressed in rounds, minutes, hours or even years. Some spells specify that their effects last until the spells are dispelled or destroyed.

Instantaneous

Many spells are instantaneous. The spell harms, heals, creates or alters a creature or an object in a way that can't be dispelled, because the magic only exists for an instant.

Further, Xanathar's Guide to Everything (pg. 77) has this to say about Simultaneous Effects (thanks to @V2Blast for suggesting this):

If two or more things happen at the same time on a character or monster’s turn, the person at the game table — whether player or DM — who controls that creature decides the order in which those things happen. For example, if two effects occur at the end of a player character’s turn, the player decides which of the two effects happens first.

This also suggests that both fireballs should be resolved separately, making separate saving throws and damage rolls as though they did not happen simultaneously, but rather one after the other as though they happened a fraction of time apart.

Finally, the Essentials Kit includes some of these rules, but with a slightly different wording (thanks @Medix2). In the Essentials Kit Rulebook, on p. 3, under the section "Effects with the Same Name Don't Stack":

But when two or more effects have the same proper name, only one of them applies while the durations of the effects overlap (a duration is a time span of 1 round or more).

Durations is mentioned again, as in the PHB quote I included earlier in this answer (from p. 205), but in this case, what counts as a duration is made explicit; "a duration is a time span of 1 round or more". This also points to Instantaneous not being a real duration, further suggesting that both fireballs would deal damage.

No, they don't

In the same section (PHB, pg. 205) that you've quoted, it also gives the following example:

For example, if two clerics cast bless on the same target, that character gains the spell's benefit only once; he or she doesn't get to roll two bonus dice.

(Emphasis mine)

This effect is similar to the Guidance spell, so Charlie will only get one extra d4.

The wording most potent effect in this scenario does not refer to a roll result, but rather to the number of dice, or a fixed effect. For example, if you cast a spell that gives a 2d4 bonus, it will overrule a spell that grants a 1d4 bonus.

Fore more information on overlapping spells and which effect is more potent, check out this question