Sounds great. Don't create whole track, just make quick samples and let me hear them first.
I won't direct you much on the music, just go free on it how you feel like. I just want it to be epic and ambient, to sound big, but not too fast or too big, because of ambience. Some horns and heavy drums like in my links would be appreciated. Don't go too much on one instrument, orchestra would go well.
I don't force you much, just give it a try if it doen't cost you much time.
Nice ideas on the sounds, if I think of any puzzle with sounds adapting gameplay, I'll let you know.