Bob is a side-effect of some of the custom code in ALttPR. He's the upper-right corner of a Heart Piece with some extra flair because he's a re-textured Anti-Fairy. He's said to be related to the code that does or doesn't do a thing if you leave the item on top of Bob's Torch on the Floor 1F of Ganon's Tower.
Some people believe that Bob has become something of a legend or mascot for ALttPR.
You find the Red Mail here. There's an optional boss in the basement of the Armos Knights. There are required boss fights during the ascent of the tower of the Lanmolas and Moldorm. The final boss fight is the second and final battle of Agahnim.