Giving Hunter Paladin styled animal companion might be for the best. The boost to intelligence + some bonus things + a template to add onto it at some level to make it a magical beast. Combined with new teamwork feats and either a reworking of Animal Focus to make it something more often used or strong since it works sort of like Judgment/Smite Evil at the moment.
I think the class could use more flavor and options. Putting them onto the animal companion and new teamwork feats is totally the right direction, but it's hard to test it at the moment since there aren't many teamwork feats that give anything more substantial than random +1s and +2s or rerolls.
The ability to talk to your animal companion would be amazing too.