The shade from the trees and fan sound like they will help a lot, Chris. You could also hang some old, wet towels in front of your fan to boost the humidity and give a swamp cooler effect. But don't be too surprised if your Phals object to the high temps. I've had mine wrinkle up their leaves for most of May and June, until we start getting rain, or at least clouds in the afternoons. They aren't dying, but they are telling you they're not happy when they do that. Most of the time they recover.
Yes, I give my whole collection a feeding of potassium nitrate with added Epsom Salts about every two weeks, alternating with the regular fertilizer now that we're into the growing season.