Water:
Try Gyarados or, as I did (with another NDS) - Blastoise.
With fire, I had Infernape, but if you have no other Nintendo DS or friend/WiFi, you may try Houndoom, as user above me said. It could have Crunch, Nasty Plot and maybe Flamethrower or Dark Pulse, or maybe even Overheat.
I don't like Flotazels, so I would give you a tip with e.g. Wingull - it is a nice, original (imho) water/flying Pokemon. But Sajmon180 said good opinion about Pokemons.
Regards