Ready made Fondue mixes are like any ready made food - generic, bland, as the vendors want to cater to as many customers / tastes as possible. So the ready made supermarket moitié/moitié mix will use cheap and bland cheeses which hint at Gruyère and Vacherin.
That's OK to be introduced to Fondue. However, Fondue was not invented by a sophisticated cheese connoisseur, traditionally it was an opportunity to use up whatever drops of wine, bits of cheese and bread (and whatever else) left over. Somebody found adding a bit of garlic a good idea, and the Kirsch was thrown in for good measure...
So Fondue is an experiment in process. As already mentioned by other posters, any cheese which can be grated can be used. Beware of soft cheeses however, I thought adding a Brie would make the Fondue smooth and creamy - forget it, it turned out to be lumpy beneath a layer of something oily.
Also the Parmiggiano (Parmesan) will not work as it needs higher temperatures to melt.
Gruyère, Appenzeller, Emmentaler, Tilsiter, Vacherin are all good to start off with. Cheeses from the Savoy region of France are typical ingredients, but I'd say, experiment with whatever you please.
As for freezing - that is perfectly OK. I discovered that keeping cheese meant for a Fondue in the freezer for a couple of weeks actually enhances the texture of the melted item - maybe not the right word: pre-frozen cheese tends not to separate so easily, that would be the better description.
As for the addition of garlic and Kirsch: Personally I wouldn't touch Fondue without a hearty addition of garlic, but that's me. Try cutting chilies into thin rings and adding that to the Fondue. Mushroom and / or bacon crisps also make a good addition. Feel free to experiment.
On a visit to Sweden I was once asked to conjure a Fondue.... how to start.... phew! Local cheese shop, try this local cheese, try that local cheese... OK, selection made. Then to the "Systembolaget" - the state-run booze pusher to find some wine, Kirsch? - forget it! Calvados will have to do...
So as for the hard stuff which goes into the Fondue - along with the lemon juice it helps to dissolve the cheese and the cheese taste is usually more powerful than the booze (OK - depending on the dosage - somebody mentioned a 25% alcohol Fondue ) it doesn't really matter.
Then there are some folks who use beer instead of wine, or even bubbly! Both work wonderfully!
Oh, and before I forget: The date printed on a cheese usually shall be interpreted as "best after..."