I can't look at your deck list, but if it's Mech Mage and all you are missing are the 2 legendary cards, they aren't hard to fill in with other options. Those are the two best cards for the job, but to replace them you have to understand what they are doing.
Dr. Boom - An expensive card in mech mage. It exists to establish a strong board presence. It can be played while ahead or behind and in either situation it is a threat that must be dealt with. So you have to look through your deck and find a card that will try to fit those criteria. Note that bomb is popular because no other card does this job as well as him.
Loatheb(Leg) - He acts as a threat. He is cheaper so can be played faster. He protects your other minions from spells while ahead. He prevents the enemy from using spells for removal forcing them to trade if you're behind.
Sylvanus(Leg) - Acts as a threat. Expensive for the stats. Has limited use when ahead, but might prevent them from playing a single big minion. Great when you're behind, forces them to trade their entire board into Sylvanus or to try and ignore her and go for face damage.
Piloted Sky Golem(Epic) - Acts as a great threat. Has mech synergy. Is a sticky minion and trades 2 for 1 or better most of the time. Can close out games quickly when you're ahead. I think this is by far the best non-legendary option.
Sun Walker(Rare) - Acts as protection. Forces your enemy to deal with it before it can deal with other minions. Sometimes the enemy won't have an answer. It does no close out games, but can delay a round which is often enough for you to get the advantage.
Frost Elemental(Free) - Acts as threat. The freeze allows you to control the board for an additional turn.
Archmage(Free) - Not a threat, but a big enough body that it's often hard to deal with. The spell damage can also allow you to reach for lethal if you have spells.
Antonidas - His primary purpose is to add value to spare parts and act as a closer to finish the game on the next turn with Fire Balls.
Gadgetzan Auctioneer(Rare) - Makes use of the spare parts to draw into the rest of your deck. His body is smaller, but he makes use of the same ideas. By cycling through your deck you are drawing threats for the next turn which you will hopefully use to close out the game. Treat him as an end game option and only play him on a turn that you can combo him with drawing cards.
Gadgetzan is really good for this and is honestly a great substitution. He would be run in all mech mage decks if Antonidas didn't exist, but generating cards you want is better than drawing cards you may not want.
