Yes, Tower is a slow faction, but their respawn is richer than average, which allows hiring 1-2 more heroes from the start and thus clearing the respawn more effectively (compensating for the low speed). So mages/alchemists crawl slowly, but they have plenty to eat :D at every step.
As for taking the Nagas, I recently took them (in a game with bRitvo4kA) on the 2nd Naga Bank on 3 with a ground stack, a scout hero (swamp dweller), and saved all the Gremlins and all the Nagas. I wouldn't say it was an easy fight, but no harder than for other castles. IMHO of course, but I tested it. ;)