I think fire will do best on strength but I haven't played the game in a while. well its not that long but still can't remember the low level magic too good. I figure its only a matter of time before people in this thread say, Ultima, Meteor, Holy, blah.

Anyways there is a few areas to stock magic in the start of the game. In the training center, Out side on grass, Outside in forest, Ouside on Beach and I think you can still reach the fire cavern after ifrit... not sure.

As for getting those powerful magics with the refine ability is time consuming.