The bigger the diameter, the lower the optimum speed. Generally, fan and propeller blades should run at a high dynamic pressure, but still at subsonic speeds to avoid the higher losses involved with supersonic flow. Since the tip will be the part with the highest speed, and propellers have bigger diameters than fans, propellers run at lower speeds.
The high pressure compressor and turbines of an airliner engine will run at above ten thousand RPM, while the propeller wants to run at about 1800 to 2200 RPM. The propellers on the Tu-95 even run at only 750 RPM. Both the fan and the propeller are powered by separate low pressure turbines which also have an optimum speed, and the faster the turbine runs, the more torque it will produce for a given size. For that reason, the low pressure turbine and the shaft of a big airliner engine run at between 2500 and 4000 RPM, and the turbine of the PT-6, a classical turboprop engine, at 30.000 RPM. Since power is torque times RPM, a faster running shaft will be lighter than one running at low speed, so the speed is only reduced directly at the propeller mount.
A fan's optimum speed is between that of the compressor and the propeller and would ideally also need a gearbox, but here the transmitted power is so high that a compact gearbox will be hard to design. Even if it runs at 98% efficiency, it will produce waste heat in the order of several hundred kilowatts in case of a big airliner engine. Some small engines with just a single turbine use gearboxes already (e.g. the Lycoming ALF507), and now the next generation of efficient fan engines are also introducing gearboxes. But so far, most engine designs have preferred to run the fan faster than what would be ideal. Note that the tip speed of a modern, ungeared fan is already well above Mach 1.
Their bigger diameter makes propellers more efficient. The more air mass is involved in thrust creation, the higher the propulsive efficiency will be. Fans need to be smaller precisely because they will run with the speed of the low pressure turbine, and to convert the available power into thrust, they need a much higher solidity ratio, which translates into a higher wetted surface, which increases friction losses.