Majora's Mask is an interesting departure for the Legend of Zelda series. It is, perhaps, the oddest game in the series, featuring many elements that are just plain strange. It was released for the Nintendo 64 by Nintendo in 2000, though it was originally planned for the N64's ill-fated 64DD peripheral. For a while, while it was still planned as a 64DD game, it was known as Zelda: Gaiden.
First, the packaging. Before this game, every Zelda game had a very similar design for the packaging and cartridge label. It featured the word "Zelda" in a large, red font, with "The Legend of" over it in a very small font, and the name of the specific game under it in the same small font, all against a background a particular shade of tan. Next to the "Z" in "Zelda" was a sword and shield. The Majora's Mask design, however, featured "Zelda" in purple and the Mask itself in place of the sword and shield, as well as a multicolored background with a drawing of a young Link (at least, that's what the special edition of the game had).
The cartridge for the first Zelda game was gold, rather than the usual gray. Ocarina of Time had a special edition with a gold cartridge, with most copies the usual gray. Majora's Mask featured a special edition with a gold cartridge as well, but the label in the special edition was a hologram with the aforementioned design (I honestly have never seen a non-special edition copy). Xenex informs me that the Australian release did not include any special edition copies of the game, much to the annoyance of Australian Zelda fans.
The normal formula for a Zelda game consists of several levels (usually around 8 or 9) of increasing size and complexity, each of which contains a specific mix of items and major enemies. Between levels the player must usually complete a mini-quest to gain access to the next level. Beyond these required mini-quests is usually a set of optional mini-quests, that give the player additional powers of varying sorts (this formula applies mostly to A Link to the Past, Link's Awakening, and Ocarina of Time, though it also can be applied somewhat to the other games in the series).
Majora's Mask almost (but not quite) dispenses with this formula entirely; it might be more accurate to say that certain aspects of the formula have been made much more important than others. For example, there are only four levels (rather than the usual eight or nine), but these levels are each much larger than a usual Zelda level. The mini-quests are far, far more important than they are in other Zelda games, mostly because there are many more pieces of heart than in the other games. In every Zelda game, you start with three "Heart Containers", which represent how many times you can be hurt. Each level gives you an extra one when you beat it. To make up the difference between how many heart containers you'd have if you only beat the levels and the total number possible, there are many "pieces of heart" spread across the land. Collecting four pieces nets a whole container. Ocarina of Time, for example, has 36 pieces of heart, and A Link to the Past has 32. Majora's Mask, because it only has four levels, has 52 heart pieces, which are mostly gained through various mini-quests.
The plot of the game is, basically, Link gets ambushed in the forest and led into an alternate world, where the moon is about to crash into the city of Clock Town. The cause of this is a little imp named the Skull Kid who has found an ancient mask of great power called Majora's Mask. After being turned into a plant person by the Skull Kid and turned back by the previous owner of the mask, Link promises to return the mask to its previous owner.
The moon will crash in three days. The interface for the game is almost identical to Ocarina of Time's, except for a clock in the middle of the bottom of the screen. The clock tells the time of day, and which of the three days it currently is. Time passes in a slightly sped-up real time, with something like a day in the game passing in 15 real minutes (this is merely a guess from playing the game). The player also has the ability to slow time down to something like half of this (one day in 30 minutes, if my guess is correct). The player also has the ability to reset the timer, and begin anew from the dawn of the first day.
That's where the challenge comes in, and where the factor that makes this one of the harder Zelda games comes in: when you travel back in time, you lose all of the progress you've made up to that point. Every level you've beaten, every person whose problems you've solved, even some of your items, they all go away or are un-done. All you get to keep are most of your items (the bow, but not your arrows; the bomb bag, but not the bombs; the money in the bank, but not the money in your wallet) and the knowledge of the songs you've learned (much like Ocarina of Time, much of the game revolves around playing magical songs). Progress is only really made when you've earned a new item or learned a new song.
Progress is also made when you earn new masks, for fully a third of your time is spent collecting the 24 masks to be found. Four of the masks change your shape into various different forms, each with their own special abilities (one of these is sort of a secret). You also recieve a special mask when you beat each of the four levels (you can't wear these masks; much like the stones and medallions in Ocarina of Time, they merely mark your progress). Some of the masks have special abilities: the bunny ears make you run fast, the bomb mask allows you to blow yourself up (when you don't have any bombs, and really need to blow something up), and so on. The mini-quests that don't give you pieces of heart will probably give you a mask.
There are many people of note in the land of Termina (the alternate world is called Termina), and they each have their own schedule over these three days. To help you organize this, the game helpfully provides a notebook which automatically keeps track of everyone of note you've met and everything they've given you. Completely filling out this notebook is perhaps the most challenging part of the game, and may require some mind-numbing repitition of certain tasks. Not going insane doing certain things over and over is another contender for "most difficult task."
This game is certainly more complex and challenging than Ocarina of Time, featuring many puzzles and enemies that are highly similar to those in the previous game, but usually with a twist that completely changes them. I actually like this game better than Ocarina of Time, simply because it offers a greater challenge. Some things in the game are inexplicably weird (the last song you learn, the Elegy of Emptyness, for example, is capable of inducing a mindfuck, and the last level is guaranteed to), but one can usually figure things out once they get used to them. For the Zelda fan, this game is highly recommended.