Those of you that are suggesting evaporative cooling must not live in nor near Houston. If you noticed his DB/WB temperature, you will notice that there is not much real margin for driving evaporative cooling, and, even if there were, the resulting humidity in the cooled air would only make a bad situation worse in that work environment.
Yes, the air would be a little cooler, but it would also be so muggy that it would be very uncomfortable to work in on a day in day out basis.
While "swamp coolers" are very common for the western more arid regions of Texas, they are not commonly seen in the coastal regions.
If you do consider going that route at all, there are those portable units that are commonly seen at NFL games in the fall, on the sidelines, when the ambients are still quite high, and especially for the southern teams. You generally have to be standing right in front of them to get any feel of the cooling effect.
There is a mold and mildew build up problem with evaprorative cooling in the deep south. Not unsolvable, but something that has to be dealt with on a continuous basis or it will get ahead of you.
However, 95 degree outside air is preferable to the 110-120F that this warehouse must get to (comparing it to my un airconditioned warehouse not too far from houston,) plus, the heated zone in the ceiling of the building (where it gets even hotter than 110-120F,) radiates heat back down onto the workers on the floor, even if the floor is at or near ambient. So, removing this heated air is a must.
You did not say how much budget you have, and it looks like all the owner wants is a few fans, so, I suggest the following.
Exhaust the heated air in the overhead regions of the warehouse, and place some outside air supply fans in such a way that the ambient make up air blows directly onto the work stations.
If you have any budget at all, then do what they do at Six Flags over Texas, an amusement park for those of you not from the region, and air condition some air and blow it directly onto the work stations, just like they do for you standing in line at the amusements.
This A/C'd air would also be dehumidified, which would help offset the WB and make the overall ambient "feel" more comforatable as it mixed with the non cooled air. (again, just what Six Flags is doing)
If I knew of a better answer I would put it in my warehouse and try it, and tell you about it. My warehouse is not a work place, and I am not often in there, so there is no cost justification for doing something elaborate. I try to stay out of the place in the summer, and when I do have to go do work there, I plan my work such that it is done in the AM, probably not an option at this location. I feel for these workers. The attic ventilation combined with large floor fans in the doors blowing directly on my work area with outside air is the best I have found. I also see it a lot in similar situations at client locations.
Best of luck.
rmw