It also sounds to me like it probably is a load that's cycling on and off. Maybe you have thermostatically controlled heaters somewhere (tank heaters? heat strips for the AC?) that usually don't operate because you're in Sunny Arizona. Do you happen to have an AC ammeter to watch the current draw? That would show pretty quickly if that's the cause.
One other possibility that comes to mind is a bit of air in the fuel line for the generator, either because the fuel tank level is right near the end of the pickup for the generator (typically around 1/4 tank), or because there's a little air in the fuel line to the generator that needs to work its way out. In the former case, the generator would stall after running for a bit more; in the latter case, the rough running would clear up.
As Gordon says, 110V is not an unreasonable output voltage under a decent load, particularly if the governor hasn't had time to stabilize from the added load.