We were there last October for a short trip. Incredible. We did the Narrows bottom-up to Orderville Canyon. We both got the booties/shoes, and my wife also got the pants, as she is typically cold as well. I had some chilly times in the morning with the cool water temps, cool ambient temps, and shady canyons. Dare I even say possibly borderline hypothermic.
We also scored a permit to "The Wave" in Paria Canyon by the mail-in lottery system. If you want, to can try and get a permit at their office by the next-day in-person lottery permitting system. I also hear that the Paria Canyon is an excellent slot canyon to do (read: remote). http://www.utahwild.com/desert_canyon/paria_canyon.phtml
Lastly, if I were to be able to get back to that area again, I'd probably do the East Rim trail in Zion, explore Kolob Canyons section, head out to Strawberry Point, and go to Cedar Breaks.