Hearthpwn

Not to parrot too much of what others are saying, but for competitive use on ladder, N'Zoth, Dr. Boom, and Loatheb are the most versatile, but deck-specific can change a lot of things. Patches the Pirate, Mal'Ganis, Reno Jackson and friends, certain Death Knights like Shadowreaper Anduin and Malfurion, Aya Blackpaw, and Bloodmage Thalnos are all cards I've seen used often enough to be of note. Of course, it all depends on what deck you make. Not all decks use N'Zoth, Loatheb, and Dr. Boom, as well. Many decks will find room for one of them, of course. Entire decks are built with N'Zoth in mind, Dr. Boom won't fit super well in aggro decks like Pirate Warrior, and Loatheb is mostly a midrange card that protects your board to hopefully ensure lethal the following turn and sometimes stave off a combo for a turn. Don't go crafting the big three just to get into wild, decide which you need first.

If you play a turn 1 Fiery Bat into this, you could give the Fiery Bat divine shield or the health buff to trade into your opponent's turn 1/2 play. Doesn't seem terrible, although doesn't fit the theme of the quest.

Rip Nat the Darkfisher, Fire Fly is the same size for the same mana cost, has 2 bodies, can be played half at a time, has no draw-back drawback, and has elemental synergies. 

As long as you own any part of the adventure, it will stay in your list of adventures even after it has rotated out of buy-able. I struggled with paying for Naxxramas by gold from quests back when it came out, and so didn't end up getting the last wing. I haven't bothered to pay 700g for the last wing yet, but it still shows up as an option for me to do so.

Mech Mage isn't a terrible deck necessarily, but the polarization caused by Mean Streets of Gadgetzan means that the majority of decks you're going to see in any format right now is either a fast, face-is-the-place deck with Patches the Pirate (even Egg Druid likes pirates nowadays) or is some Reno Control variant featuring Kazakus as their end-game ultimatum. Mech Mage still exists, and is a fairly good (and relatively budget-friendly) deck.

Not all decks need Dr. Boom. Many decks do use him, of course, but many decks don't curve that high. Any N'Zoth deck is usually glad to have the doctor, of course, but Egg Druid, Pirates, and many Reno decks simply choose not to run Dr. Boom. There is no 'must-have' cards in wild in the sense that every deck runs them, but Dr. Boom, Loatheb, Mad Scientist, and Sludge Belcher see play in many different decks, and are good first choices of cards to craft if you're just getting into Wild.