Sounds like a bad fan clutch. After you price one, think about putting in an electric. It's fairly easy, works great (I've been thru a summer in N Alabama with mine), and I could feel a small engine power difference. The archives have a ton of info on the install.
The fan will always spin with the engine running especially when cold. When you rev up the engine the clutch allows the rpms to rise without the fan holding it back. The fan will eventually catch up to the engine rpms. A sign of a bad clutch is a fan that spins freely when the engine is off or one that doesn't spin at all. There should be a noticable resistance to turning when cold.