Nintencats is a total no-brainer. The only speedbump is cats don't have the same opportunity for different versions. No one really cares about cat breeds. But then I hate it when multiple versions of the same game come out so I wouldn't care. Ideally the two games should connect so that your cat and dog can play together, fight, whatever.
I think some sort of hamster like game would work well too with mazes and wheels and tunnels and all those other cool things hamsters interact with. The game could have hamsters, mice, gerbils, guinea pigs, etc.