On a 15-frames/stride cycle it seems that both front feet are on the ground together for 3-5 frames, and both back feet are on the ground together for 5-7 frames. In this way the feet spend roughly the same amount of time in the air if the dog is walking fast or slow (around 5-7 frames in the air). When a walk slows up, the dog takes smaller steps and spends more time with its feet on the ground. Hence...
|F per stride||F on the ground||F in the air||F both feet on the ground|
|12||~6-8||~5||~2 (front) ~3 (back)|
|15||~8-10||~5-7||3-5 (front) 5-7 (back)|
If you leave the feet hanging round in the air too long the walk starts to look stiff, like the dog is stuffed and artificially held in pose. Remember the dog 'weighs' something and it needs to drop that leg to support itself on.
Here's some rotoscoping I did on a 15 frames/stride cycle. I then adapted the the walk to a 17 frames/stride cycle which divides up much easier for 2D animators who don't have the computer to in-between on 5ths and 3rds.
I found this amusing clip on youtube of a fat dog being asked to walk very slowly...
Note that the legs still move fast through the air, but just very slow on the ground. They have to move fast to prop up the dog's heavy body, which would otherwise fall over. The strides also shorten up a bit, but not too much. There's an interesting discussion about whether the back paws of a tiger step into the footprint left by the front paws here. It would seem that the size of the step doesn't actually vary that much as the spacing of the footprints is used to estimate the size of a tiger - obviously if a tiger walked with different step sizes depending on its speed, it would make it impossible to estimate the size of the tiger!
There's a whole load of really detailed information on quadruped locomotion here at 3dcognition, and here on Stuart Sumida's site.
UPDATE: In a newer post I've expanded a whole lot more, and written a basic tutorial on animating a dog's walk.