I kinda did okay, up till the first quest with the water units and having to kill one (or both) of the orc leaders. First time, I ran out of time. Second time, I tried rushing the orc leader on the island and all my sea units died.
This sounds like scenario 4 "Bay of Pearls" in the heir to the throne campaign, it's probably the first really tough challenge. There are a few (somewhat ancient) threads on the official forums that may be of interest, and I found this familiar post:
For Bay of Pearls, the answer is to fight on your terms rather than the AI's. I opened the first 3 cages, sending 3 or 4 mermen to the northwest (I've tried keeping one merman back for defence, with moderate success). I had about 200 gold, recalling my most experienced troops (including 4 level 2s).
As long as you keep the mermen at least a full movement away from the enemy units arriving from the sea castle, I've found that they can avoid fighting until they reach the 2 nagas guarding the NW cage. I try to keep the mermen in the NW of the map for a couple of turns or so, until the first wave of bats and nagas have hit my main force on the landmass.
My land forces are usually enough to wipe out the bats and nagas, you can usually tempt the nagas onto the land for easy kills, or just use mages or marksmen to nuke them out of the water. With enough forces available, you can destroy these guys before the orc forces arrive.
After making several unsuccessful attempts at holding the line against the orcs, I decided to take a different approach. As soon as the bats and nagas were wiped out, I instead withdrew my forces to the small stretch of water between the castle and the mainland (using the island village as the central point). It usually gives you an extra couple of turns before the orcs arrive (crucially getting you out of the night into daytime). The other advantage is that you now have a more defendable frontline of 5 hexes. With tough enough units in the frontline, you will be able survive the initial enemy attack. In your turn, simply rotate the injured units out of the line, and strike back at (hopefully injured) enemy units in 20% terrain.
Meanwhile, the mermen in the northwest should have made their move as soon as the main force of nagas and bats are engaged with your land army. I usually take out any stray nagas and bats first, before opening the final cage. I try to attack the sea castle leader in daytime, when his maximum potential damage is 24, using storm trident followed up by melee attacks if he's down to low hps. Merman activity near the land is usually enough to draw some orcs into the water. This will have the useful effect of taking some pressure off your land forces. From here the scenario is straightforward to wrap up, so it is usually where I start making mistakes, it is quite easy to over extend your forces when they go on the offensive. The second orc leader is usually a little more risky for your mermen to attack, as he tends to have more units guarding him.
Here's a thread from 2006 about the "no losses" HttT challenge
https://forums.wesnoth.org/viewtopic.php?f=3&t=11641A 2016 thread on bay of pearls may be most relevant
https://forums.wesnoth.org/viewtopic.php?f=3&t=44312 I've recently started another attempt on HttT hard, amusingly I completely forgot about the trident in the NW corner of the map in bay of pearls, but I had enough gold and high level units to overwhelm the land orc's army, so no need to deploy the merman assassination squad. I'll have to replay it and pick up that trident, it's a little too useful to ignore. The Isle of Anduin, the preceding scenario, is a good one to "fill your boots" exp and goldwise - I stumbled upon an effective strategy whereby you send elven cavalry directly south as a distraction, with your main force heading west then south with Delfador to deal with the leader - the AI sent too many troops after my distraction force allowing me to win easily in the west and notch an early victory on turn 13.
Let me know if these replays work:
HttT-The_Elves_Besieged_replayHttT-Blackwater_Port_replayHttT-The_Isle_of_Alduin_replayHttT-The_Bay_of_Pearls_replay