The lack of charisma is certainly another factor and that I'd put down to the actor himself, all hair and no style.
One thing that I noticed when I was doing the Joe Cuts was that a number of scenes of Byron communing with his people were cut. I think if maybe there'd been more of those scenes people might have accepted his leadership abilities more. Remember, too, that much of what was the basis for the teep colony was the cult that JMS was in when he was in his 20s so that might account for some of the creepiness factor.
Why is it everybody picks on Byron's hair, though?? I mean, Brown Sector was habitable enough for the colony to live so there was obviously plumbing. We know that only high ranking crew (and probably luxury transient quarters) on B5 got actual water showers and the rest got vibe showers so why wouldn't the teeps and Byron be able to keep clean even without a lot of money? Who knows, maybe there was even a negative ion setting that took the place of hair conditioner.
The hair is the last straw in a heavy handed characterization. He is, like his name, a byronic hero. This list taken from wiki:
high level of intelligence and perception
cunning and able to
adapt
sophisticated and educated
self-critical and introspective
mysterious, magnetic and charismatic
struggling with
integrity
power of seduction and sexual attraction
social and sexual dominance
emotional conflicts,
bipolar tendencies, or
moodiness
a distaste for social institutions and norms
being an
exile, an
outcast, or an
outlaw
"dark" attributes not normally associated with a hero
disrespect of rank and privilege
a troubled past
cynicism
arrogance
self-destructive behavior
He fits the list to a tee, and just annoys the same way TOS's "Let That Be Your Last Battlefield" Byron is too set up as the tragic martyr. I was longing for someone, anyone to take the clown out. I get it, bad things happened to Telepaths, heck he even helped do it, but he and the telepaths aren't the only ones suffering. Being aware of that as an audience member, his pleas and later Lyta's come off as whining pity parties. The hair just makes him look like a Fabio cover boy, which coupled with the character purpose makes him a ripe subject for ridicule.