Fates are generated every 5 to 10 minutes in every area. The best place was west of Fallgourd? in North Shroud as that area was small enough to run to the FATE in less than 30 seconds but the area is a level 25 to 30. This site here has maps of each area and where the fates are located. Same with primals and what each area is best for levelling up in for what levels.http://home.comcast.net/~nakomaru/ffmaps/
Seriously, I can't run 5 steps sometimes without running into a FATE. I've had them actually spring up around me a couple times when I was trying to do other things (quest, arrange my inventory, etc.).