Finally finished the game last night. I was able to complete the game without save states or a guide, but I had to sink many hours into the game. I do think I got more out of the game that way. I really enjoyed the over-world exploration in this game, and that's what I spent the bulk of my time doing, just wandering around casually fighting enemies and uncovering secrets. There were tons and tons of secrets hidden throughout the world. Almost every screen had something to find, even if several of them got your horns stolen, it was fun to uncover as many hidden staircases as possible.
I also had fun wondering what each item would be in the palaces. The item I mentioned being excited about earlier in the thread was the Ship. The balloon item you get later, and was somewhat disappointing, but I don't think I would have been able to find the final palace without the mini-map. Still, it took hours for me to find the palaces in this game, which got really frustrating towards the end, but helped me uncover all sorts of other secrets, like magic and armor upgrades.
My biggest gripe with this game was the combat. I didn't mind it nearly as much once I found the axe, but then the game has you get upgraded swords, which I found much more difficult to use than the axe. I was so happy when I found the golden axe in the last palace, as it actually made me feel vastly more powerful than I had been up to that point. I didn't have much trouble with any of the palaces except for the sixth and the ninth. I kept dying at the end bosses of those two and having to run back through the palace, while trying desperately to get to them with decent hearts/magic.
Overall, I did really enjoy this game, despite the times I became really frustrated (considered quitting completely a couple times). I'm glad I stuck to it, because it was a rewarding game to beat, and I really enjoyed losing myself in the game, while looking for secrets, villages, and anything else interesting. Since, I played the Golden Axe beat-em-ups as a kid, it was fun to see some familiar bosses from those games as palace bosses. I doubt I'll play this game again completely through, but I may pick it up from time to time for a bit of fun.