Nightmares- Nightmares are Enderman-esque creatures that roam the Badlands. Like Enderman, they appear black and thin. However, unlike Enderman who will stalk upon being provoked, Nightmares will stalk anybody in the Badlands and fly instead of teleport. According to Grayson, they are souls that "he" (presumably Herobrine) stole. For what reason is unknown at this point.
The primary method of attack for a Nightmare appears to be launching flaming, smoking Netherack blocks that upon contact cause severe burns. This doesn't seem to be the end of their capabilities, however.