I enjoyed Blade of Destiny the most as it had a the most content and lots of optional dungeons.

Tweaking some of the purely random aspects sounds good, how about a system where if you fail 3 times then the next time you try you are guaranteed to get the skill up once. I remember times where I failed to level up a skill across multiple level gains, that was no fun at all.