His rule in Ala Mhigo is generally considered far better than his contemporaries, especially since he took the country without bloodshed. It was Nael and Zenos that completely ruined the territory, though I'm not saying there weren't issues like some of his men being willing to just look the other way instead of take action against a mob. As far as the Beast Tribes go, the entire idea of the Ultima Weapon was to absorb their Primals so they wouldn't have to constantly go to war against them.
Who exactly did Gaius murder? I think it was stated he was ordered to kill various heirs to the imperial throne, but I'm pretty sure you're talking about killing people in imperial invasions here. The Waking Sands maybe? But that was Livia, we don't know what orders he gave her in that regard.Yes, because Gaius is a murderer and warmonger.