All these shows (and other works of fiction) go back, at most, around 2,500-3,000 years. Anatomically modern man, so-called homo sapiens sapiens, is usually thought to have arisen around 150,000-200,000 years ago. So from an evolutionary viewpoint, these timeframes are mostly irrelevant - people haven't changed much between early Greek times and the Middle Ages, and neither have other animals. It's just too brief a period for major evolutionary change.
What has happened to animals over that time is domestication - the artificial selection and breeding of animals, which began (according to Wikipedia), around 6000 years ago. I'm not entirely sure what horses looked like back then, though. Genetically they were similar to today's horses, but since we can see huge differences between different horse breeds, even though they're the same species, we can suppose that Spartan horses in the 6th century BC might have been different from horses used by Scandinavians in the 8th century AD.
As for the question of how long they've been on Earth - it's hard to answer. "Horses", of some definition, have been around for millions of years, though only at some point could they be considered identical to today's horses.
And as for why you keep seeing them everywhere, whether in historical accounts, historical fiction or history-inspired fiction is just because they're so useful. Horses were used by any civilization they were introduced to because they are strong, reliable animals for work and transportation. Goats are used for milk and meat and keeping greenery under control. Man domesticated animals for their usefulness, and horses and goats, alongside the rest of the farmhouse gang, are very useful.