Susanne Shultz and Robin Dunbar at Oxford University studied "encephalization," which is how much a species increases its brain size over evolutionary time. If your ancient ancestors had pea brains, but nowadays you have a giant brain (compared to your body size), congratulations! Your species encephalized. Since it costs a lot of energy to power a big brain, scientists assume that highly encephalized species are getting a big benefit out of those brains in the long term (say, by inventing tools).
Shultz and Dunbar conducted a statistical analysis that included 511 mammal species. Within groups of related species, they included fossil data from extinct species as well as data from living species. In all cases, they looked at how the size of an animal's brain, relative to its body size, has increased (or not increased) over time.
They found some groups of mammals that had clearly become more encephalized over time, and other groups whose brain size had stayed the same. The orders of primates (such as monkeys and apes), cetaceans (whales and dolphins), Perissodactyla (horses and rhinos), and carnivores (carnivores) all had increased their brain sizes, with primates increasing the most.
When the groups were divided into suborders, a few things changed. Among the carnivores, for example, the Caniformes (dog-like animals, which include wolves, bears, seals, and skunks) seemed to account for all the encephalization. The brains of Feliformes (cat-like animals) had stayed pretty much the same size over time.
So what separated the brain growers from the brain slackers? The mammals that had encephalized were social animals--they live in groups, packs, or herds. Those with solitary lifestyles had not encephalized.
Though relative brain size is connected to intelligence--big-brained animals do tend to be smart--it's not the only thing that matters. The study authors don't conclude that these animals are smarter than less-encephalized ones (horses, after all, are still dumb as rocks). But they do conclude that the brains of social animals have grown the most as they evolved. Something about living in groups, it seems, requires some extra equipment upstairs.
How does this apply to your dog and your cat? Housecats weren't actually included in the study. But they actually have slightly larger brains, relative to their bodies, than dogs do--even though their brains haven't grown over evolutionary time. As for dogs, they were just one of many dog-like species included here. And since domestication tends to shrink brains, cats and dogs are probably both dumber than their wild cousins. But we love them anyway!