If I didn't know anything else about them, given the choice between two people who "don't do bikes", I'd take the fence guy.
Bikes have several places, like the seat stay and chain stay junctions with the seat tube, that are hard to spray paint. A painter, even a good painter who's not experienced painting bike frames can have voids or runs in those areas. I suspect that the nature of powder coating would eliminate that problem.
Bikes are made of tubeing. Tubes have four sides so a painter who is used to working flat surfaces could have trouble. I'd assume that a fence maker would be experienced in working with round tubes.