In mid-April, most things will be opening up in the high country (Sedona is a lower altitude but still doable).
Sedona has some decent rock and some crap. You have to really choose.
Oak Creek Canyon (between Sedona and Flagstaff) has a mixture of sandstone and columner basalt. There are some longer stuff on sandstone, and one of the best cragging cliffs that no one has heard about (unless you are from Arizona) is the Oak Creek Waterfall, though most of the routes are on the harder side (the routes are between 5.10 and 5.13 with the vast majority of the routes between 5.11 and 5.12).,
In the north country by Flagstaff is a really good place to hang out (especially by then) called Paradise Forks
http://www.summitpost.org/mountain/rock ... Forks.html . The climbing is very high quality climbing (some of the locals who lead trad deep into the 5.13's prefer Paradise Forks to Indian Creek if you can believe that) with very high quality climbs in the 5.9 and 5.10's (especially on the Pillow Wall (though shorter), and the Prow and some stuff scattered between the Davidsons Wall (although some of the best climbs are located here and on the Prow) and Gold Wall. The area is also heavy in 5.10's and 5.11's (and quality 5.12's but that is outside the posting question)
A note for those reading this in mid March: as of last week the road was pretty difficult to do with high clearance 4WD. I'll be checking the access with a Subaru before the weekend (3/20) unless i'm in Indian Creek. By next week the access should be acceptable. Otherwise as of a week ago you could get within 2 miles and then ski in.
Prescott has some good climbing (ie: Granite Mtn) but the areas will be closed then due to raptor nesting, expect toopen mid-July to mid-August.
If you need a tour just drop me a line.