To me, the main reason Magic is fun is the variety of skills and approaches it encourages. You can play it as several different resource management games: there are at least 4 important resources to manage (time, mana, cards, life) and you can win by focus on getting one or more of these resources more or by preventing your opponent from having/using any resources, and all of those decisions have major impacts on your play and deckbuilding style. You can also play it as a game of assembling your crazy exploit of the rules fast enough to win (combo decks), or you might even be able to exploit the rules so hard you're essentially playing a different game from your opponent, so you have a completely different win condition to achieve (legacy Dredge).
Deck construction really is one of the more creative aspects of MtG where you can create new kinds decks or twists on old ones
Very few games embrace the unknown dynamic nature as well as MtG did. They would introduce cards that could be mixed with past-future cards almost on a whim, creating moments of pure frenzy as people managed to build systems that seemed indestructible.
It's crazy to think how much some of these cards are worth now: http://www.mtgprice.com/sets/Beta/Savannah