When Brahne decides to kill Kuja, he shows his power by coming out of Bahamut's attack (which successfully destroys the entirety of Brahne's fleet later) unscathed except for a cut on his head.
But really, Kuja isn't the type to fight face to face with someone. Instead he manipulates entire kingdoms into doing his dirty work for him. And he has power over the Mist, the Invincible, and the Black Mages.