The fan will run with smaller voltages, it will probably even run at 5v but at low speed.
Forget about cr203* batteries, they're designed for <10mA of current.
Forget about powering the fan from a 9v battery, it's expensive and low capacity and if you want them to last you shouldn't draw more than 100mA constantly.
I'd suggest changing design to a 4xAA or AAAA batteries. With rechargeable batteries, the maximul voltage will be about 5.4v which is below what most microcontrollers and ICs can handle.
If you use regular batteries, you may want to use a low drop regulator because 4 regular batteries would give up to about 6.5v which is a bit more than some microcontrollers and ICs can handle. You can find 5v ldos that have only 0.1-0.2v drop so they'll do 5v fixed just fine. Or you could use a LDO in both cases to drop to 3.6v or some lower voltage.
The fan should run from 5v but at low speed. You could go for a cheap lm25** boost regulator (you can find them on eBay for a couple of dollars) to boost the 4-6v to 7.5-12v