I just came back from Sedona, which might be OK if you go spring, not summer.
We rented amazing bikes for about the price of schlepping on the airplane. Much more convenient, you get a really nice new bike, and don't bang up your own bike travelling and riding for days. Someone suggested adventurebus to us.