The micro clock determines the instruction execution time, and that determines the loop time, which can consist of many instructions. Depending upon the type of micro, it can take one to four clock cycles to complete one instruction.
Running a lower clock speed can reduce the power requirements. You never want to run at a higher clock speed than the maximum rated, as micro operation can become erratic.
The reason for odd crystal frequencies is that they often are divisible by a simple binary counter to get a desired lower frequency. If you divide 32.768KHz by 2^15 (a 15-stage binary counter) you get exactly one pulse per second, so that frequency is used for most battery powered digital clocks and watches. Other odd crystal frequencies are related to certain types of RF or digital transmission that require specific frequencies.