1. I don't understand your problem with the party make-up; you have a combat cleric, a sorcerer with skillpoints and an ability to use Cure wands, a gish, and a paladin.
Considering how you labeled that the superlative "Worst. Party. Ever." on the merits of the class combinations alone, I have to view this:
I won’t even mention the horrible backstories.
With some skepticisim.
2.
Isn't adventuring dangerous? So what's suprising about PCs doing something dangerous?
3.
This sounds like you wanted them to ask you what they should do. IE, you wanted them to do what you think they should have done.
4.
CRs are static, but EL's are not; if a CR creature fights the PCs in an environment higly beneficial to the creature, then the EL is not equal to the CR, but rather higher than the CR.
I'm not suggesting that it's unfair to throw a high EL at the party, just that you should know that you're doing it. I feel that a burrowing creature encountered in an underground environment may very well rate this; I suspect a large, burrowing giant with a template represents more than an EL 4, and likely more than a CR 4.
5.
I would like to say that the players will
never know when they reach the, "we can survive this encounter" threshold, and expecting them to wait until they reach it is unrealistic.
---
Nothing you did in particular was unfair; you had a challenge lined up for them and they went after it early, and were killed. But your tone had something of a, "they weren't playing correctly" element, which can be troublesome in a DM. Remember that you have much more information than they do, and so their decisions can seem foolish when you look at it with the benefit of knowledge.