These days no-one likes a bully, but the word bully was once (17th century) a word of endearment or familiarity - like sweetheart or darling, which could refer to someone of either sex. Later on it came to be used only with reference to men, implying friendly admiration - fine fellow or good friend, as the OED puts it. It often prefaced the name or occupation of the person being addressed - there are several examples in Shakespeare's works - bully doctor and bully Bottom for instance.
The OED says that the etymology of the word bully is unclear, but it's possibly from the Dutch boel, meaning lover (of either sex). It doesn't come from the word bull, which probably has an Old Norse origin, according to the OED.
The sense 'fine fellow' soon developed into 'blustering gallant' or 'swashbuckler', including, in the early 18th century, one who protected prostitutes. By the late 18th century we find 'bully' being accompanied by more negative adjectives eg swaggering, low-minded and unscrupulous.