I highly suggest the 5870 - I got one used off of craigslist for $150 and it can preform at ~350 MH/s (and is good for gaming to boot!)
I did both. Temps were so high I unloaded the cards and got 7950 Sapphire Dual-x
why do you care about temps as long as they run fine? they are built to withstand lots of heat, people worry too much about temps because they read it on the internet. were you getting lots of stales or something?