How long does it take to breed a new type of dog? Does it take longer to change the size than to simply change the colour, etc? Did chihuahuas and great danes start out as normal-size dogs?
Thank you. 
It’s unclear how long dogs have been distinct, genetically, from wolves. At least 15k years, but it could be as long as 100k. It does seem that a likely scenario is that dogs were domesticated from wolves in western Asia sometime in the last 20k yearrs, and that it only happened once.
Many modern breeds of dogs have only been around for a few hundred years.
It doesn’t take very long at all.
There’s no simple answer. Dogs. Like other animals, are normally bred by finding a desirable trait in the population and selecting for it over the generations. How long it takes for that trait to become fixed into a breed depends on how complex the genetics are. If a trait is simple recessive then it can become fixed in one generation. If the trait is dominant or complex then it will take much longer to fix the trait.
So for example you could change the coat colour to white in most breeds very rapidly, provided that occasional white individuals were thrown up, because white is recessive. However changing the coat colour from tan to brindle could take much longer because the genetics is complex. Similarly you could breed a change in size through ‘Dachsund’ legs into a breed very fast, but changing overall size would take much longer.
It’s just basic selective breeding. Every generation you select the individuals that most closely fit what you desire and breed form them alone. Ultimately you will get what you want but that could take anywhere from 1 to 1 000 generations. It’s not necessarily going to be faster or slower to change coat colour than size or vice versa.
Chihuahuas and great danes, and all other breeds, started out as basic grey wolves. That’s your normal dog. They took various paths to get form there to what they are today.
How long does it generally take from genetic stability (Two WhyDogs produce only other WhyDogs) to recognition of a new breed? Do dog societies jump at the idea of a new fido, or is it a torturous political process to get your pooch his own place on the ballot?
(Occurs to me: I’m not sure if this is a hijack, OPoster, feel free to tell me to get my own freakin’ thread!)
I missed this before, sorry.
It takes decades for a relatively easy one - easy being defined as the originator having chosen characteristics (size, color(s), personality, etc.) that are generally found together in extant breeds, and being really good at the process of culling.
I suggest you check your library for a book about Herr Dobermann and his creation of the Doberman Pinscher. It took most of his life, AFAIR, but he was very careful both in how he defined it, and how he chose the breeds from which he chose the dogs to breed together.
Another example is the Jack Russell Terrier, though not quite so remarkable an achievement as the Dobie.