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:
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.
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.