fire giants weren't made of lava or anything, so i see no reason why they should radiate heat. as well, i don't see the genie as being especially thematic...
how about loki as a pretender? in effect, he went over to the giants' side. perhaps stealthy, death magic, heat and cold immune...