Actually, you rarely see fish Pokemon out of the water in the cartoon. Take your Lanturn, for example. Some episodes and movies of Pokemon also take generous time to show Water type Pokemon in the ocean, especially for the Hoenn regio series. Some that you did mention, though, do levitate. Cloyster and Sharpedo levitate off the ground for unexplained reasons in the cartoon. Cloyster can be seen in the biker gang episode in the Kanto region series battling Psyduck on the bridge. Sharpedo... I just remember it floating. Also, Misty once had a Goldeen that rarely came out of it's ball, but I remember it flopping around on dry land.
Also, if its any consolation, every Pokemon in Heartgold/Soulsilver follows you around (some not in buildings, though). That was an unnecessarily long answer.