I remember Air's Rock being slightly frustrating, but I think I liked it the best. :3
The puzzles were moderately difficult and not too easy like Gaia's Rock or annoying like Magma Rock (with its darn moving panels on lava that takes forever and a day to just cross), and you get to fly around. :D
I think Magma Rock took me a bit longer than Air's Rock and Gaia's Rock to finish; around an hour I think? (Mostly running back and forth. Now it only takes me about 20 minutes or half an hour, but still...bleah...) Air's Rock took half an hour while Gaia's Rock took 15 minutes at the longest.