>Take fire pokemon
>rival has water pokemon
>find grass pokemon
>train
>???
>profit
Best bet over a water type is Electric, since every water type pokemon is capable of learning at least 1 type of move that is effective against grass. Most being able to use Ice, Magikarp using Bounce (Flying) and Seismitoad using poison. And Electric is only weak to Ground, so it's slightly less likely to take double-damage from most opponents.
Against Blastoise however, being a pure water type, Electric is best.
Find a Pikachu and train it Raichu, or a Magnemite into Magneton, or Voltorb into Electrode.
I always choose a fire-type as my first starter in a new generation/game, so, I generally look towards getting an Electric pokemon to use against my water opponent. Swampert was the only one who foiled this. >:c