I would suggest Bold nature because Waterfalling Gyarados needs to be owned. Your best bet is a 2hko without investing sp.atk as it does...
Damage: 267 - 314
Damage: 69.53% - 81.77% to Bulkdos....Expert Belt, if you were desperate enough...
Damage: 319 - 375
Damage: 83.07% - 97.66% to Bulkdos. Mind the fact that this almost guarantees OHKOs on all quick Gyarados.
Deoxys-E@Leftovers
Bold
252HP/168sp.def/88def (this set would give you 304HP, 258def, and 257sp.def I believe, plenty to let you take something like a non-boosted waterfall.)
Psychic
T-bolt
Spikes
Recover
I sorta BS'd that by going by max wild stats and making them look even. Hopefully it's a good suggestion. However, those stats only give you 396 max top speed without EVs, so you might wanna work off the EVs above if you wanna be quicker.