Any ability that determines whether you hit an opponent in combat or not is likely to be the most important in any gamebook (unless the book itself has lots of situations where non combat stats are important. The closest I can think of is The Screaming Spectre by Dave Morris where the correct use of spells means that you avoid most combats. Also the Citadel of Chaos (FF2) is OK with a low skill if you have a high enough magic score and the correct choice of spells and so is the Sorcery! series as long as you have, once again, the correct choice of spells)
In Fighting Fantasy books, where skill is the combat attribute, you could complete most of them with a maximum skill score even if all of your other scores are at their miniumum, but some books might become impossible, even if you max out every stat apart from skill and have your skill at a medium value.
As mentioned above, the importance of speed is balanced out by the need to be able to overcome an opponent's armour and inflict damage on them too meaning that speed does not have a monopoly on being successful in combat (whereas in Fighting Fantasy books, skill is the only stat you need in combat and if you have a low skill, then you are stuffed.)
In terms of difference is speeds and how likely you are to win, if your speed is below an opponent's speed by 3 or more, then you are unlikely to win the combat.
The table here - http://4.bp.blogspot.com/_kHBgD4ZFvTs/TLdCSq-EcnI/AAAAAAAAAAU/zUlZelBZcXU/s1600/Probabilities+table.bmp
shows the probability of winning, drawing and losing a round depending on the differences in your speed (it says skill because I did it for Fighting Fantasy but the same principles apply.)
If your speed is 3 below an opponent's then you only have a 15% chance of winning a round.
You might be able to win a straight fight if your speed is 2 below an opponents and since this is Destiny Quest where you could have tons of stat boosting items and abilities, if you enter the combat with the right stuff, you could win.
I think Michael has done a great job with adding abilities and items that make winning combats possible even if your speed is lower than an opponents. Issues with legendary monsters may be resolved with the right strategy in the book or it may require some minor tweaking.
However, the idea of having a store place is great as that means that you could focus your abilities in order to fight different opponents. That is something that I would like to see.