What if you found a few zombies, then later on found an even bigger zombie, possibly a mutant? Not only would this bring a whole lot of action to Minecraft, but each mini boss would have it's unique trait, or ability. For example, zombie mutants would be able to summon zombies rising from the ground, skeleton mutants would be able to unleash a hurl of arrows at the player, creeper mutants would be able to cause massive explosions, lots of cool stuff related to the mini version of itself.
The mutants wouldn't be common and would most likely spawn at night either at dungeons or a biome that most likely fits them. Once the mutant is defeated, along with its minions, a few fireworks would go up into the sky, surrounding a chest filled with loot (mostly empty slots, like ordinary chests in temples and such). Depending on the boss difficulty, the loot would go from wooden armor and weapon sets to diamond armor and weapon sets. Most of the mutants would be difficult to beat, with the creeper mutant being the weakest. This addition to minecraft can attract many PvE players and such, and would be a challenging obstacle to encounter along the journey.