My first reaction was the Dalmatians as well. I have 2 Goldens and they tend to chase the horses, same with my Lab Poodle cross. I recently adopted a couple Dals and they are great. They require a lot of exercise so running along by the horses is great for them and they have the endurance to do it.
My brother in law has had nothin but heelers and heeler mixes....they are one person dogs, and his never left his side...They followed beside his horse and kept their eyes on him the whole time...they were wonderful....he even took them when he rode in parades and they never got distracted..
Mr Bailey has a border collie wich is good...but on the trail he runs all over the place and sometimes he scares the horses when he jumps out of the bushes...but a super sweet dog....although he hasnt figured out that "the stare" doesnt work when herding horses!
Me...i want a heeler or australian shepheard....But currently I raise miniature dachsunds...suprisingly my little stud pup goes everywhere I go and falls right in with my horse...lol...my horse is 16.5 hands and my pup only weighs 6 lbs....so you can imagine how funny it looks with them walkin side by side!
I would say Lab. They are a little bigger but if you find a good laid back one you will never be disappointed. I would opt for a 2 year old once they have that puppy stage out of them. Lab pups can be a bear but they are the most perfect dogs. I have 2. Very loyal.
I have a collie who is respectful of the horses, obedient and people friendly. He's got good stamina and doesn't chase wildlife (at least not far), so he doesn't get lost.
Any dog you get will have to fit your lifestyle and your home. Do research into any breed or mixed breeds you're interested in. My collie's big drawback? Burrs.
I ride with 2 labrador retrievers, one great dane and and aussie. The aussie is the biggest trouble maker with other dogs. I only take her when we ride into the forest where there are no trails, and likley no other people or dogs. The Labs are the best, friendly, love swimming in the rivers and stay close by.