Imagine, you leave your fort and head west a few miles, when you hear a blood curling roar. You ignore it and continue on your way. You hear it again, only much louder. This time you get to the top of a mountain and look to your left. You see a MASSIVE face of a tremendously large beast. It stares at you, watching you timidly pull out your stone sword. You step back and it leans forward to sniff you. It then turns and walks away.
Much later you head back to challenge it. You yell to it that you challenge it to a duel. It agrees and says that you keep everything except your diamond equipment if you lose. If you win, treasure.
You are then taken to a large field with hills and a destroyed tower. The beast roars. You run to cover, get your bow, and spam arrows. Even though you dealt MASSIVE damage, it merely stumbles and continues it's march to you. With a swipe of it's tail, you are dead, back at your spawn, with everything but your diamond equipment.
MUCH MUCH later you challenge it again, finally defeating the beast, you warp back, nearly dead, with little supplies. You receive it's treasure, a super item. You marvel at the beast as it saves you from a pack of monsters, then, when the sun is up, depart.
That's another idea I had. Scattered about the world would be massive creatures of great power. They make sound to attract you to them. The reward it great, but it respects you, so loss is minimal. However, they would have hundreds of heath, and very powerful attacks, immune to flames and drowning, have attacks that target those underground, have a weak spot, and even after defeat it would stay, and you could challenge it again.
The size would be large like a mountain, and the would be so rare, that most would find 1 or 2.
Well, this seems good but needs some work maybe less story. Dragons have been confirmed by :Notch:, and the Golem and Yeti have been suggested by the community already. In fact, the Yeti is my suggestion. For more info, check the link below.