THere are calculations but it's a bit complicated. Just make it big. (like 1000uF) or bigger like 4700uF, or even bigger. THe bigger the load, the bigger the capacitor.
THe diodes just need to be faster than the AC input frequency. THe same thing goes for the capacitors. THey have to be of a type good enough to handle the input frequency (larger capacitors at higher frequencies end up looking like open circuits and that does not help). That's about the only reason other than cost why you don't want a capacitor that is too big.
Did you have a capacitor at the end of your full wave rectifier? If you didn't that would explain why your fan wouldn't run. It'd be almost like repeatedly connecting and disconnecting the fan from a battery at 120Hz.