I rented the three types of horses by saying Hi, Rent, Yes over and over again until the NPCs Appaloosa (Venore) or Palomino (Thais) gave me all the horses colors. I used 8 characters it took me 190 tries in total among all my characters to get all 3 horse types because sometimes the NPC won't give you a new color so you have to keep trying. One thing to keep in mind is if you say Hi, Rent, Yes the first time you'll always get a horse. It typically went in this order: Dark Brown, Light Brown, Gray Horse. However, every now and then the order would change up. I even got the Gray Horse first once! Here's the picture for proof:
Remember, it took me 190 tries in total to get all horse types for all characters. I used 8 characters to test this out. I'm not good at math so I made you a chart. The numbers will symbolize the amount of tries it took per character which I used 8 characters so there's 8 rows (left to right). Columns (up and down) symbolize each color (Dark Brown, Light Brown, Gray) What I want you to get from this is it seems to be random what type of horse color you get first but Gray seems harder to get on the first try. Ultimately, if your okay with spending 500 gps each time you try to rent you will be able to get all horse colors. You won't know what color it is until you try. It doesn't matter what type of colors are in the barn. Please let me know if anything needs to be clarified!