Yup, you've gotten some good advice so far. For me, personally, I try not to focus too much on a specific gender or color or whatnot but think of the traits that are important to me and then look at a lot of horses until one jumps out and says "Love me."
I wasn't even looking for a horse when I found my first mini, Kody. He wasn't a good choice conformationally with a weak rear end and locking stifles, but that was my soulmate looking out from under that thick forelock and it felt like I'd been hit with a ton of bricks. I'd seen and handled a lot of minis before and never had that happen so I paid attention!
He had other positive traits to counterbalance the negative (he was humorous, courageous, intelligent, had nice scope and reach at the trot, really used his long thin neck and naturally hooked his clean throatlatch, etc.) and I decided he was worth it. He's still worth it seven years later and always will be although his body did not hold up to the work I asked it to do and he's now partially retired at only 11 years old. I sure love that horse though! He has never, not ONCE, failed to come through when I needed him. He's a pain in the @$$ when it doesn't matter but when the chips are down he stops all the shenanigans and is right there going "Where do you need me, Mom?"
Now obviously you want a horse who is built to do what you want and stay sound while doing it, but I find so much of my enjoyment comes from having that special "meant to be" relationship with my equine partner. I searched for my first riding horse for six months, test riding a couple a week at 10 years old until finally I found one that was beautiful, sane, kid-safe, experienced and also clicked with me. There had been several I really liked but they just weren't "right." Keep an open mind and as others said, look for a certain level of experience and a certain sort of temperament and ask your guardian angel to handle the rest.
And remember: a good stallion makes a GREAT gelding!
Leia