Like a lot of people I'd never had a problem with the battle speed in Zelda until SS. The worst thing about SS as far as combat went was starting the fight and getting in that first blow. As soon as you landed that first blow it was quite fun to 'roflwaggle' the Wiimote to take out some enemies, especially the fat bokoblins. though by the same token it was also annoying when they eventually blocked and reset the fight to a pokerface game of getting the next hit in. Difficulty in SS would have been better if when the bokoblins got a hit in on Link that they also went into a frenzied melee on you, i think that kind of danger would have made the fights at least a bit more intense.
I had a similar experience with the Skulltula. At first, it was very difficult to kill them, and it took a bit to actually figure out how to deal with them. Once you did figure them out, however, they became a joke really fast. That's kind of my feeling of many of the enemies in the Zelda games so far; they've become a one-trick pony, and I'd like to see them have more than just one attack up their sleeve. The idea of a frenzied state is an interesting idea, though I wouldn't want to see that happen to every single enemy.
That was my experience as well, except it was more with the skulltulas and how to actually hit their weak point. Once you learned how to kill one (by flipping them over with your sword), they became a joke rather fast. While they are in one way a step in the right direction, I agree that having certain enemies have a "frenzy mode" might spice things up.
But personally with combat as a whole in the 3D Zelda games i'd really like a complete change in terms of an engine change. I think a Zelda game would work really well in a Devil May Cry, Bayonetta style game. I don't mean by giving it over the top action (Link isn't that kind of character) but having more enemies on the screen at any one time in any one place with a large array of moves to take them all out would be a wonderful change to proceedings. Of course there is a problem with using a DMC/Bayonetta engine, in that the exploration and idea of the overworld could get completely kicked out of the game all together, but really i think nintendo would do well to completely change the way combat is done in Zelda, even making Link more athletic ala Prince of Persia in Two Thrones where he was able to crawl over enemies and slash at them from behind of kick off of them to get some respite from the battle. We've already seen Link vault over the fat bokoblins in SS to score hits from behind so a 'free-form' fighting style isn't totally outside the realm of possibility
Link has already proven he can do parkour. Honestly, I would find that a good mechanic to throw in there. We've always been given the impression that Link is very agile, but it wasn't until SS that we were actually able to see that. While I don't know if going for a free-form combat system would really change anything, I do agree that some form of change needs to be done, not just in combat speed alone.