I think you need to separate the concepts a bit.
"What is an algorithm" is best explained with the simple recipe analogy you've already used. It's not sexy, but let's be honest, neither are recipes in themselves.
"Why is what I do creative" is a completely different matter, and not really a question of algorithms specifically. Why is cooking creative? Cooking could be described as "coming up with recipes", couldn't it? (you may not write the recipes down, but they're there in the food you created. And even when you try to follow existing recipes, the result still depends on the small tweaks and adjustments you make). And what you do is "coming up with algorithms". Your job is not to implement Quicksort over and over. It is to come up with the right algorithm to use. Sometimes that may mean using an existing algorithm, such as quicksort. And sometimes it means coming up with a new one that fits your precise requirements. Similar to how a chef at a restaurant's job is not to blindly follow the same recipe over and over, but come up with the right dishes, based on what the customers want, what ingredients are available, what he served last week, and just what he feels like.
But another point is simply that you create. An architect has to respect the laws of gravity, the strength of steel and concrete and so on. No matter how much he wants to, he can't make a 4 mile high building using cheesecake as a foundation. A painter has to respect the limitations of the canvas he's painting on, and the colors he use, the structure of his brushes. And his canvas will always be two-dimensional no matter what he does. Even the best chef is limited by the ingredients at his disposal. Every other art form is limited in what they can create, by the world in which they're working.
You're not. You create everything out of a vacuum. If you want to create a "world" in which the only rules are, say, a bank's business rules, then that's what you do. If you want to create a fully interactive 3d game world, then that is what you do. And if you don't want that world to obey newtonian physics, then you simply don't implement it. If you want to create music you can do that. If you want to create a program that's able to write music for you based on the rules you set up, then that is what you do.
And you can do all this using a common tool found in almost every household, costing a few hundred dollars.
Yours is the only art that has complete freedom to do whatever you like.
In fact, ask your mother to name an art form that is allows more freedom and creativity than yours. Anything she can think of, you can do better. ;)
Imagine what Mozart would've been able to achieve if he'd had a computer at his disposal. If he could generate any sound, and if he could simply write down the ideas, the rules he was thinking of, and then let the computer take them to their logical conclusion.
That's the creativity sorted out.
Another aspect that makes programming interesting is the problem/puzzle-solving one.
Of course this will mostly appeal to people who can see a certain fascination in maths. But I think most people will still be able to appreciate that "if you like solving puzzles, you'll find programming fascinating".
Going back to algorithms, use as an example one of the everyday services we now take for granted, like Google Maps being able to finding a route from A to B for us. Sure, a human can just look at the map visually, and draw an approximate route. But the computer has to treat it as a giant graph. At each intersection, it can choose several new directions. Which one should it try? How does it determine this? What if it chooses the wrong one? How can it even find out that it's taken the wrong route, until all combinations have been tried? All these possibilities add up to an insane number of combinations that must be tried before the optimal route is found. Far more than even the fastest computer can deal with. And websites do this for thousands and thousands of users concurrently. Coming up with modifications to this process to make it possible to do this in realtime should be a fascinating puzzle for anyone who has even the slightest interest in maths or combinatorics. And even if you don't, you should be able to see why it'd be fascinating to someone who does, and why it involves a whole lot of creative thinking and puzzle solving abilities.