In response to the crits, GP criting is kinda what gives him his power, since he doesn't have a natural attack speed steroid. It's no different from Yasuo, or Tryndamere, or honestly Jax's ultimate for that matter. However, that's besides the point, the point you were trying to make is that his E is powerful, but feels lousy, and honestly, I don't think his E has much of a place in his kit the way it stands. It's like what you called my Grog-Soaked Blade changes: powerful, but inelegant. If Gmag scraps GP's E, I'm not going to be Rioting at Riot HQ, is what I'm saying. I had an idea of turning his E into a Quinn vision granter and Elise rappel combo with a knockback (like he was rappelling to the Crow's Nest, and dropkicking his opponents on the way down), but I felt that was really bloated. I'd like something like that to keep his piratey theme going, and something about that theme should go to his E instead of him shouting "PREPARE TO BE BOARDED!", firing his pistol up in the air, and turning pain train on for his entire team. TL;DR, he just needs a better E, and I don't care enough about it to feel strongly any direction they go.
his Oranges have a 30 second cooldown, but it was already 22 seconds without the cooldown lowering mechanic you suggest. (I actually kinda like that mechanic though. Its pretty neat.)
One of the inherently toxic problems you'll find out about GP if you play him like I do (the right way since I mentioned I kinda mained him) is that his W's cooldown is how should we say, negligible. If you actually wait and use his W only when he's immobilized, or under some really heavy slow or blind, you'd never get caught. The enemy team would blow all their crowd control on GP, he'd eat oranges and be k, and he'd laugh all the way back to base (a personal favorite thing for me to do would be to quote Captain Jack Sparrow in all chat after I successfully disengaged their entire team 1v5). When I finish any of my 4 Gangplank builds, he always ends up with 20% CDR. On an 18 second base cooldown, that's what I'd like to call "I'm never going to have to worry about crowd control ever again." Hence why I took out the passive CDR from leveling, and instead gave the passive some oomph via extended trades. If GP actually duels people and doesn't just sit behind his team Qing to QQ all day, his Oranges are going to be much more useful. Also, the CDR will pack more of a punch simultaneously. This change is a nerf, yes, but it's something I REALLY hope Riot implements.
In all, it feels like the kit you proposed simply added power to Gangplank without really adding opponent interaction or tradeoffs.
It's not going to solve all of GP's gameplay problems, I'll let the balance team figure that out, but at its core, it's a damn good place to start. It's going to take a champion that was considered so toxic to the game environment that Olafing was the only solution, into a champion that is flexible; yet isn't overly safe. Great in teamfights; yet not with a Garen skill ceiling. A bully laner with great dueling potential; yet gated by skill and core gameplay mechanics rather than mana.