I think having two big military factions (cats, birds, moles) is useful for balancing control of the board somewhat. Other than that I’d say you could pick whatever looks interesting to the players.
I’m not a fan of the vagabond either, because everyone else has to expend lots of energy to keep them in check without any immediately clear benefit to them. That means that what usually happens (in the games I’ve played, anyway) is that people start ignoring the vagabond until it’s too late to prevent them running away with the game.