During Season 4, Episode 12, "The Sting," they show a funeral for Fry, complete with mourners in the back. You see a total of about 5 women sitting back there. His ex-girlfriend that followed him to the future, the woman who took over for Hermes, an Amazonian woman, the old lady that's always smoking, and a 5th that I don't remember. I also know that Fry dated Amy, and, as you mentioned ,his grandmother. So altogether I would go with at least 7 affairs before finally getting with Leela.
I don't remember his affair with the radiator, but from the image you can see (from right to left)
1) the amazonian's arm
2) the 20th century ex-girlfriend
3) Morgan Proctor (the woman who took Hermes job)
4) someone I don't recognize
5) Smoking woman(was setup with Fry by Bender when his head was attached to Amy's shoulder)