Matt:
Check with a local outdoor sign company that paints large billboards.
They should have the most experience and be able to tell you what paints
are most durable in your climate.  They may even have a painter that can
do the mural for you if you have a photo of what you want.  As far as
painting the mural, check with the art department at a local college.
When I was in Nebraska the head of the art dept. at Hastings College did
large outdoor murals.  I don't believe he is physically able to do them
anymore.  Someone local may be as talented.
Greg Shuman, Exhibits Director
DHDC
Amarillo, TX