I'm not certain that describing the fight as "Deadly" for your level is wholly inappropriate; however, there is some Math we need to knock out first.
Frost Giants are weaker than their Challenge Rating would suggest
In the Dungeon Master's Guide, the advice for creating custom monsters provides advice on how to stat creatures based on what their Challenge Rating should be, including a table for basic stats:
If all you need are simple stats for a monster of a particular challenge rating, follow the steps here. If you want to create something more akin to the monster stat blocks in the Monster Manual, skip ahead to the "Creating a Monster Stat Block" section.
—Creating Quick Monster Stats, Dungeon Master's Guide, pg. 274
A few things stand out immediately, comparing to the Frost Giant's Stats:
- The Frost Giant's health is too low (138 vs the expected 176-190)
- The Frost Giant's AC is too low (15 vs the expected 16)
- The Frost Giant's Damage is too low (25x2 vs the expected 51-56)
- The Frost Giant's Attack Bonus is too high (+9 vs the expected +7)
The only major feature is the Net†, but it's an optional feature of the Frost Giants introduced in a specific campaign module, meaning it's not been considered in the original CR calculations. Other than that, the Frost Giant does not have any special features or abilities, aside from a (trivially unimportant) immunity to Cold Damage, meaning that in addition to lower than expected stats, it also doesn't have features that aid it.
† Brief Editorial on the Net: you described it as "some ridiculous version of net with a DC 17 Strength check to get out instead of the normal DC 10.". I'm not really interested in adjudicating the capabilities of this feature and how powerful it is, but it's worth noting that this is the stats provided in Storm King's Thunder (pg. 246) for this ability, so while it is more powerful than a normal net, it's what the campaign designers intended. I don't know whether your party is using that campaign module or not.
The damage and attack discrepancies mostly equal out to the expected offensive capabilities of a CR 8 creature (damage is equivalent to a CR7, Attack bonus 2-greater-than-normal means add 1 for an Offensive CR of 8) but the health and AC instead are representative of a CR5 creature. On average, that puts a Frost Giant around more of a CR of 6.5 than 8, meaning that budgeting encounters using their normal CR is going to result in easier-than-normal fights.
In fact, using the normal budgeting technique:
- 2,300XP for a CR6 creature
- I'm rounding down because in my experience, low HP tends to count more than low DPR in terms of affecting encounter difficulty
- x3 for 3 creatures, 2,300x3 == 6,900XP
- x2 for Group Size of 3-6 creatures, 6,900x2 == 13,800XP
- Deadly Encounter threshold for a party of 4 is 1,700XP per party member, or 6,800XP
With all these adjustments, it still seems like the encounter should be relatively deadly—but I would argue that that's a pretty reasonable assessment given your account of how the fight went.
Deadly is an appropriate description of how the fight went
Bear in mind that your Paladin went down in a single turn! You were able to recover him with some judicious use of healing, but it's not hard to see how this fight could have gone very south very quickly depending on the context. If the third Frost Giant had chosen to attack the Paladin after they went down, before the healing, they would have all-but-certainly died, and this "Deadly" encounter would have lived up to its name.
Deadly does not imply unwinnable, it just means that the fight will require some very apt strategic aptitude on the part of the players, or some degree of sheer luck, to prevent any member of the party from dying. Your party managed to survive the fight, in part because your party appears to be quite well balanced, with characters that have either exceptional survivability (Paladin, Rogue, Fighter) or plentiful healing capabilities (Cleric, Paladin) or high Damage output (Paladin, Rogue) or potent support capabilities (Cleric, Paladin). In total, unless your party has abysmal ability scores, I would expect this party composition to punch above their pay-grade, so to speak.
One last thing I should mention: the thresholds for per-encounter design are important guidelines, but also important is the XP-per-day thresholds, which imply strongly the maximum amount of combat a party can take over the course of a day—which they very well could blow in a single combat encounter given an especially powerful foe. Indeed, for a 7th level character, the XP-per-day threshold is 5,000XP, and multiplied by four characters, puts the total at 20,000XP, which now exceeds the budget provided by the three Frost Giants under my calculations (13,800XP), and is only slightly eclipsed using the original total (23,400XP).
So in total there's a few important takeaways:
- Frost Giants aren't as strong as their CR ought to imply,
- The encounter rated as Deadly, but as less powerful than what it should take to exhaust a party of all their resources for the day,
- But it's still fair to call the encounter Deadly, especially given how much damage got poured into your paladin in a single turn, and how differently the fight could have gone with less luck on the part of your party,
- But also your party is well-optimized to handle an unusually dangerous encounter.
So take a small amount of pride in knowing that you fought back against a threat that was above average for your level, but also remember that things could have gone much worse.