Raiding Underwater (with Raid-command) by CyborgSellout
Overview: Usually when an underwater nation invades a land nation, there aren't many ways fellow land-nations can respond. Raiding underwater from the coast is one of the few ways to do this. Underwater nations often don't protect their borders, leaving them vulnerable to limited-commitment raiding, and in the long term, destroying the shallow coastal provinces can also help protect the land nation, since armies in those underwater border provinces will be difficult to supply.
Strategic concerns: Using Raid-command from a well-patrolled coastal fortress with access to many water provinces is the ideal positioning. If the enemy water nation has the ability to respond quickly, it is advantageous to be able to switch the target province every turn. Ideally, the enemy water nation is also heavily committed to invading someone else, but attacking from a patrolled and forted province is one of the best ways to protect raiders. The underwater nation can respond with a small force, teleporters, or assassins, but troops on Raid-command shouldn't engage in battles outside the fort.
An Implementor Axe on a Mound King can be a cost-effective choice; they're fairly cheap for size of the pillage bonus and they usually kill around 300 population. (Successive raids reduce the effectiveness, but also reduce the chance of being caught, so multiples can be effective)
Land nations may have access to units with the pillage ability, but in most cases barbarians and Barbarian Chiefs are going to be the easiest non-national way to access pillage/raid commands. They're not sneaky or fast, but they can use the Raid command, have a pillage bonus, and they're very cheap, even if Pills of Water Breathing are not.
Pills of Water Breathing are probably the cheapest for barbarian use. 5 barbarians and a chief can still kill a meaningful amount of population, and should evade moderate province defense. Still, in order to kill 1000 population a turn, 6 or more groups may be needed, though the unrest will also help reduce the income in the short-term. The cost of 6 Pills of Water Breathing may seem expensive, but the effects of raiding are long-term, so if the game is expected to last at least 50 more turns only a couple of successful raids are necessary to be cost-effective over time. In multiplayer, other land nations are usually willing to help fund anti-fish activities, so if you don't have access to water pills, try asking around.