Personally I would rather see the game made generally harder with longer growing times, more aggressive wildlife (would it be possible to nerf trading so things are more expensive?) rather than just getting seiged by unkillable horrors early on and that being the end of it.
I agree with you (one of the reasons that I started the Orc mod rather than just using Better Goblins). I'm hoping that the wraiths just come in and take your lunch money (so to speak) at the beginning, and turn into an incentive to devote a lot of resources to your military in the late game. If they start being early fort-wipers, I'll have to tone them down (or raise their progress triggers). Ideally, they will be something that comes to your fort and takes what it wants and then leaves at the beginning, and then a constant threat to your woodcutters/fisherdwarves/caravans afterwards (and thus a good reason to dedicate a squad or two of champions to patrolling around). They should be killable by well-trained and well-equipped dwarves, though. Perhaps even easily, if they are good enough with swords or axes.
Longer growing times and less-valuable food/booze/dye will also probably go a long way towards making both survival and trade more difficult. Giving dwarves [SLOW_LEARNER] would also probably help a lot to reduce the number of legendary dwarves you have lying around.
I'm not sure if amphibious mounts would work, since (in my experience) the mount code is a bit hacked-together (similar to the caravan wagon code), so it seems like everything involved needs to be able to path for it to function well.
Permanently paralyzing dwarves, especially from a vermin, would be really annoying, not hard. Hard gives you a challenge to overcome. Permanently paralyzing vermin would be
Goddamned Bats.