The main issue in a game like D&D is that dogs become utterly useless pretty quickly and die too easily. Is this any different than people? Well that depends...
I believe in using Mythic Animals
So why can't a dog gain levels and have a class? Don't just go right to "Warrior" either. In my most recently completed campaign one of the bard's had a dog for one of his henchmen. The dog was part priest. It would howl and bay to drive off the undead, a turn undead (equivalent) in a party with no cleric was quite useful.
It shouldn't be hard to picture a dog Paladin, I mean..all dogs do go to heaven. What about a dog ranger or druid? A heroic level 7 dog shouldn't be beyond the realm of imagination either. What real logic could you apply to a human (hairless ape) gaining increased power and levels that you could not apply to a dog.
And don't leave this to just dogs, perhaps look to Lovecraft and have a kingdom of cats. Mr.Whiskers is an NPC just itching for use after all. And who wouldn't like a high level horse?