I SOLVED my fan Problem. I decided to clean my computer on the inside. While doing so, I decided to look up how to take out the front cooling fan on the internet, and I stumbled upon this article
http://macsaregreat.com/?p=63
My fan problem was caused by a solid layer of dust built up on the heat sink of my ATI Radeon X1900 Graphics Card. If you go to the article linked above, you can see a picture of how it looks.
If you aren't looking for it, you will easily miss it because it will be a solid layer of dust covering the heat sink (plus its not the best viewing angle to see).
I cleaned the heat sink to my card, booted my computer, fans ran loud for 5 seconds and then slowed down and started running quietly!
I can't vouch for other video cards, but this totally fixed my problem, even the booting up twice problem!