You don't have to use aquarium sand but you also can't use just any old sand. Sharp sand can harm the fish, especially loaches and cory's. it can harm their barbels and even cause them to get infected and rot. There are several other options though, and there are several threads on here about it. Children's plays is what I personally use, as i like the colour and find it good for plants to root into, but there are other possibilities. As for when to do the change I would personally allow the cycle to complete first before changing it. Most of your bacteria will be in your filter with a small amount being in the gravel itself.