I advise grinding outside the chocobo ranch (near Kalm) until level 30 -- this goes fast if you try to unlock a few limit breaks using hyper and cover. Then you don't need to dodge the Midgar Zolom on a chocobo, you can just beat the bastard, and get Beta at the same time. (Make sure your character with the Enemy Skill material doesn't do much damage before someone gets kicked out).

Later, after you get the buggy, drive into Costa Del Sol on the buggy and stow away on the ship to Junon. Very near where you come out at the Junon ship, you'll see several Shinra troops drilling. Beside them is a...red thing. Press it, and alarms will go off and you'll start getting strong (for that level) random encounters, giving 80-160 AP per fight, and a fair amount of exp and gil. You should have some double materia growth gear at this point, so you can master a bunch of them. I went to level 50 there before setting foot in Gongaga. At level 50, you can easily one-shot the boss in Cosmo Canyon with a limit break. It also basically means you'll never have to level again. This is the best place to level on Disc 1, but by the time you hit Disc 2 regular enemies will be just as good.