80C is average for today's GPUs, I have an 8800 that hovers around ~70C in a heavily cooled case.

As for the fan setting, it's probably already set for to the highest speed then and that is good that it starts right away.

Really the only other thing to try, other than an external cooler, is to apply some Arctic Silver to the CPU and GPU as MarineOne mentioned.