A palomino is a color, but can also be a registration, like pinto (not paint though mind you...paint is an actual breed). Palomino and pinto are colors, but they are color registrations. You see lots of saddlebred, arab, and QH crosses registerd as pintos and palominos, when really they're a grade horse with color.
A quarter horse would suit your needs perfectly as they are strong, hardy, and level headed. I would suggect staying away from more thoroughbredy QH though as they have a tendoncey to be more hot and less suited to an 'outdoor' work load if you know what I mean. Try and get what's considered an old style QH. They aren't as pretty, but they were bred to be the cowboy horse; to go over all kinds of terrain looking for cattle. Any stock horses (appys, paints or QHs) have these qualities. Old style work horses like these also have more endurance, and don't have such short bunchy muscles made just for speed. That's why appys can be attractive, because they orignated as a wild breed, and therefore have a tendocy to be more hardy, and can go longer distances on less.
If your thinking about any kind of crossbred, you might want to consider a draft cross, which would make the horse stronger. I would also suggest getting getting a horse with darker pigmentation (bays, browns, blacks). I know that palominos are attractive, but horses with lighter pigmentation have a tendoncey to have softer feet. Many paints are like this.
I would suggest a horse for you 15.2+ hands, with excellent feet, and a strong back.