The first Legend I ever opened was Lorewalker Cho. I disenchanted him to help me make Ragnaros. I have always been more of a control player so I think I made a good decision. It's funny because now I don't use Rag at all in any deck but for a while there he was a total horse for me and certainly allowed me to win a lot of games.
I think Leeroy is also a good choice. If you know what type of player you are (Control vs Rush) you can craft accordingly. Leeroy if you like fast decks, Ragnaros if you like slow decks.
Cho is the only Legendary I've ever disenchanted. I have a gold Al'Akir and a gold Tinkmaster. Muukla is really the only Legend that I am missing that could see play in a couple-few decks. I also lack Van-Cleef but I literally never play Rogue so, meh.
I went a very long time without spending any money on the game but then I started to kind of fall in love with it so I finally caved and decided to purchase enough packs to make most of the cards I wanted. I have a few holes in my collection (still only have one Sea Giant and it took meforeverto get my first Brawl) but for the most part I have all I need to make pretty much any deck I want.
I won't necessarily disagree with playing Constructed to start, but I personally started with Arena myself and, yeah, it isn't always the most cost effective in terms of gold right at the start, and yeah, you'll lose a lot. But you'll get to see and play with such a wide variety of cards that you likely would never see in Constructed that I honestly think it is the best way to jump into the game. And once you can get to at least 3 wins consistently, you're earning packs and paying your way towards the next Arena run. And as always, in Arena, I recommend making your mana curve look like it's giving you the finger.