I can't help with suggestions for a place to stay, but I can tell you that there is some wonderful hiking in (around) Sedona. I went there for a quick long weekend back in February of 2004 (or should I say crazy considering I started on the East Coast...).

If you're interested, I have a small photo gallery from my 3 seasons in 3 days in Sedona - the first day was sunny, the second rainy, and the third snowy. The gallery is at http://denise.smugmug.com/gallery/81583. And there's a link from the gallery description to my blog if you're looking for more details.

Happy planning and dreaming...

--- Denise