This is a good time for the Hermit Trail. I agree with Pika that it is more scenic than the BA. While the weather should be ideal, I have seen snow during the last week of May on the Coconino Plateau.

You might consider something in the Gila Wilderness. Trail heads are available at a variety of elevations (5000 to 8000 feet) and it is extremely pleasant country.