(Earth) Earthgift Shrine is by the temple of Chaos where the game starts. You need to beat this one 4 times to fight all the bosses. 5 floors.

(Fire) Hellfire Chasm is on one of the islands by where Bahamut's cave is. You need to finish this one twice. 10 floors.

(Water) Lifespring Grotto is in a whirlpool near Melmond. You need to use the ship to enter. You need to finish this one twice again. 20 floors. The two hardest bosses in the game are on floor 20 here, Shinryu and Omega.

(Wind) Whisperwind Cove is in the river system by where Mt. Gulug is located. only need to go through this one once to get all the goodies, it is very long with 40 floors. This does include non battle floors, like a town of mages that sells every magic spell in the game.