Anything with Grab will be able to attempt a grapple as a free action after a successful attack without provoking an AoO. Big Cats are a popular choice because they have a lot of natural attacks, start off with Rake, and get Pounce as well as Grab at level 7.
I like monstrous scorpion from vermin hunter. If you start as a human or halfling you can give them +2 intelligence right at the start and they will progress as any other animal companion, both pincers have grab, and a tail sting with poison is nice too