It took me a long time to beat the Marsh Cave on the NES. I believe I owned the game for ~4 years before that happened. Everything after was a cakewalk.

Overall, the game seemed more difficult on the front end. After you beat the Ice Cavern, it's not so bad, especially when you get weapons/armor that you can use as magical items.

BTW, has anyone ever beaten the Ice Cavern before Gurgu Volcano? I did it on my last playthrough for the first time. I wonder if it's possible to beat Kraken & Tiamat before facing off against Kary?