Storm Surge, my two suggestions for you are:
1. Kricketot, which must evolve on the same Route as you catch it on. It must also know Sing and Night Slash. Nickname it Beatlecrek.
2. Yanma, which must evolve inside of a Gym. It must have Tinted Lens as its ability and keep Detect in its moveset. Nickname it Bugbuzzard.