Lucario - Adament - 252 Attack/252 Speed/4HP
Swords Dance
Close Combat
Extreme Speed
Ice Punch
In regards to water pokemon I've got an Azumarill sitting around, back in the day I used to use a Starmie a lot also, this was back before I had any clue about EV's and IV's and just battled against my friends. Since you mentioned a water type in that other thread I considered a Rotom Wash as I see that quite frequently.
Lucario should be Jolly to take advantage of its Mega form's good 112 Speed.
Recommended Wash Rotom sets:
-Volt Switch
-Hydro Pump
-Will-o-Wisp
-Pain Split/Rest
Nature: Bold
EVs: 248 HP/216 Def/44 Spe
Item: Leftovers
or
-Volt Switch
-Hydro Pump
-Thunderbolt/Pain Split
-Will-o-Wisp
Nature: Modest
EVs: 228 HP/60 SAtk/220 Spe
Item: Leftovers
or
-Volt Switch
-Hydro Pump
-Thunderbolt/Hidden Power (Ice/Fire)
-Trick
Nature: Timid/Modest
EVs: 4 Def/252 SAtk/252 Spe
Item: Choice Scarf