Here's an interesting hypothesis: Would Speed still be that important if the calculations of which pokemon goes first was handled in the same way the game determines the success of a semi-accurate move?
I mean I kind of find the Pokemon games to be mostly luck-based to begin with, such as when the power of a Pokemon's attack fires between 85 and 100 percent power each turn, when a taunt effect or confusion status decides to finally disappear, and when the Treasure Hunter on Route 13 gives you a different item from what you really wanted from him every day. If the effects of a trainer's outcome in the game is mostly determined by the roll of a dice, then doesn't the rule of giving the pokemon with the most speed 100% authority to land the first hit become more of a hindrance to the overall games' luck favored motifs?
Anyway, suppose that the decision of which Pokemon goes first was followed by a formula or two that predetermines that first move by a random number. Higher speed pokemon would simply have a higher probability over slower speed pokemon, but the game's choice of a number between 0 and 10 could allow for the slower pokemon a chance to use it's heavy attack before it's faster opponent without the need for a priority +1 move or trick room. I kind of see the formulas playing about something like this:
Priority of player 1's ability to move first = PL1's PKMN'S Speed * Random Number / 100
A random number between 1 and 10 would determine the total of Player 1's Attack Speed Number.
Priority of player 2's ability to move first = PL2's PKMN'S Speed * Random Number / 100
A random number between 1 and 10 would determine the total of Player 2's Attack Speed Number.
Then whoever ends up with the higher Attack Speed Number goes first.
If you can picture something similar to a battle between pokemon like Cacturne (slow) and Terrakion (fast) with this formula in mind, you might find a light of hope for the Cacturne landing that OHKO Energy Ball before surrendering to that killer Close Combat.
So I would think that this major change in the speed rule could make battling more exciting and full of tension while still valuing the importance of speed for all pokemon, but at the same time making the battles a little less stale. Of course priority+ moves would go first 100% of the time, keep that in mind. I find that this concept of speed being a luck based status works out alright in older RPGs like Dragon Quest, and it doesn't necessarily make those games anymore difficult than they already are, so if this was how the Pokemon battles functioned from now on, I could live with it.