I'm in AZ too now actually, and my wife's civic was overheating so I had to do some troubleshooting as well.

So is the car actually overheating...as in the temp indicated on the guage goes up the hot rather than staying closer to the cool?

Try testing the fan with jumper wires from the battery. It should run smooth and fast. If there is a "weird noise" or if it is really rough or something, you might need to change the motor. If it runs smooth with power from the battery, then start looking elsewhere, like the relay, thermoswitch, etc.

At least jumper the fan motor and swap the relays and then tell us what happened.

What about the AC condensor...when you let the car idle with the AC on, does it fire up okay after a while?