With the right equip and strategy, you can beat Galamoth at pretty much any level. I think the lowest I've beaten him at was something around level 38. It's hard to get to him being much lower than that unless you just mist through the entire second castle with the goal of getting to him ASAP. Which is quite doable.
I leveled up about 20 times when I beat him. SotN's EXP formula is unique in that the lower level you are compared to the enemy, the more EXP you get. Since Galamoth gives a ton even when you're equal in level to him, being way lower makes him give an astronomical amount.