I have some YGO cards too, and while I only played while decks were all the same (Black Hole, Monster Reborn, etc), it still reminds a 40 cards deck. The game is bound to be always similar at one point, and the newer decks (E-Hero, Monarch, etc) often require too specific cards to be viable, problem you do not have with magic. Magic also has around 15,000 cards, as far as I know, too.
The color wheel is indeed a good concept, although I find a lack one thing. Black > Green > Blue > Red > White > Black. I still find it hardly developped. Another thing that annoys me is the lack of methods against control deck (I'm not talking about blue counter, but more like Standstill, Opposition, Pegasus...) in some of the colors unless you make a deck for that solo purpose. That and stand-alone winning cards (Umezawa's jitte). Considering I don't play in any format (just with the cards I have, we don't have black lotuses anyway) and with fun decks (whose purpose is not lock the game for 30 turns).
Cards such as Millstone is not that great anyway, btw. Welcome to 2008.
Lastly, a suprising part is the MTG storyline. It is very well developped, very flexible (just add another plane in the multiverse) and mostly, very original. I've read Kamigawa, Ravnica, Time Spiral, summaries of all older sets, soon Lorwin/Shadowmoor and I have yet to find any comparison. It could hardly find any cliche, not the main, big ones at least.