Did you follow the IFIXIT guide for your system? iMac Intel 24" EMC 2134 and 2211 Hard Drive Replacement. Double check the HD thermal sensor connection and the placement of the sensor to make sure it is working correctly.
What HD did you use to replace your old one? Was the SATA I/O speed the same? Your original drive was a SATA II (3.0 Gb/s) you need to replace it with the SAME I/O speed drive or one that can be adjusted to SATA II, or the slower SATA I (1.5 Gb/s). A SATA III (6.0 Gb/s) will appear to work but will cause the system to over heat as the CPU & HD will be fighting with high retries (reads & writes).
Since you noted less of a problem after letting your system sit for a while is a symptom of a mismatched SATA I/O HD problem. You see the indexer process needs to re-index all of your files you just installed or copied over. Once the index has managed to complete the HD I/O will be much less.
As to cleaning you need to be careful with vacuums as they tend to be mini Van de Graaff generators. Which can be very deadly to computer systems. You should get a can of Can'ed air to blow the build up away after using a soft paint brush to carefully scrub the dust off. Don't spin up the blades to high or long as you can damage the bearings. As lubing the fan bearings you really can't and any oil that is exposed will collect dust and will foulup the fan.
Lastly, check your EFI firmware level & update if needed, follow this Apple TN EFI & SMC firmware updates for Intel-based Macs. While it won't effect your problem, you could resolve other issues if it's not up to date.