Go for the Agility first. Pets like Ethyl, Clyde, Wrathjaw, Valkin, Haze, Ribbit, Horton are all great pets. Since you would go Agility, you can make up that lost of Crit with a crit pet like Clyde, Ethyl, Ribbit or Horton.
Best bang for the buck would be Ethyl.