The biggest success factor (in terms of deck composition) is in the versatility of your deck. You never know what class you'll play against. Ideally, you want a single deck to be able to stand up to different playstyles from different opponents.
That's not to say that each deck, including your own, doesn't have its own weakness to certain other decks. But the key is to try and minimize the amount of decks that you are weak to.
Mages have notoriously tough secrets to get through (they are the class with the most expensive secrets after all). Comparatively, Paladin secrets are a bit annoying but hardly ever a big game changer. Not saying Paladin secrets can't be good (I'm a devout Paladin player), but a random paladin secret will give you less bang compared to a random mage secret (ignoring the different mana cost).
Ice Block, as you mentioned, can turn the tide of a game quickly (or, more accurately, stem the tide of a game that has turned against the mage). Especially if you are playing an aggro deck, every turn counts. If a mage can guarantee stalling you for one more turn, that gives them the freedom to counter your plays without fearing defeat the next turn.
Assuming turn 10+; a mage that played Ice block can spend their next 17 mana (7 from the turn where they play IB, 10 from the next turn) wiping your advantage off the board. There aren't many boards that can stand up to the equivalent power of a (flamestrike)+(fireball)+(fireball)+(flame cannon). The mage might of course play different cards, but these cards will presumably have a roughly similar bang for buck.
If they play any freezing spell during their 17 mana blowout, this can add another 10 mana per stalled turn.
However, I don't expect a mage to expect a Flare. This means you can catch a cocky mage (who plays balls to the wall because IB is protecting them) and surprise kill them.
It's perfectly acceptable to use the same card differently when playing against a different opponent. This can be based on enemy class (most common) or enemy deck type.
As a mid/control paladin, I keep a Noble Sacrifice in my hand against druids and warriors, but I tend to play it early against a rogue or hunter.
Ice block is a really annoying secret. You can influence the outcome of most secrets (Mirror entity = play a tiny minion; Noble sacrifice = attack with the lowest attack minion first), but Ice block is pretty hard to influence (except for making sure your opponent has the lowest health possible before triggering IB).
I wouldn't suggest keeping Flare in your opening hand if you intend to use it lategame. But I do think it's a valid idea to only want to play the Flare against a seemingly unavoidable Ice Block late in the game.