I recommend a 4x4 or 5x5 embark so that you can have a greater variety of biomes and room to build more interesting defenses. (High velocity flying objects in general need a lot of room), but that will hurt FPS in the long term. Having enemies or entire armies poof into existence inches away from the fortress really hurts the sense of immersion for me.
Consider using Biome Manipulator (
http://www.bay12forums.com/smf/index.php?topic=164658.0 ) to help figure out or modify your embark to maximize the fun. In particular, evil biomes are not always interesting, because reanimation and evil weather are interactions that are generated randomly. One thing this helps make possible is a partial evil embark where your edge tiles are evil/reanimating, but you've got a handful of non-evil biome tiles in the middle of the embark where you can butcher/dump corpses without infinite undead animal bits.
Evil weather is mutually exclusive (a region can have rain or evil clouds, but not both). Evil rain is generally harmless to mild, and evil clouds are either more serious illness, or thralling. For challenge, you want thralling, and for even more challenge, pick a thralling dust or liquid and turn on WALKING_SPREADS_SPATTER_DWF:YES in d_init.txt. My favorite "real" challenges in past versions have been from thralling dust spread making it past the decontamination pools.
Embark near enemies and (in theory) send raiders to attack everyone else and get their attention. Probably embark far away from other dwarves so enemies actually come after you instead of hitting other targets. Getting sieges reliably is a pain in the butt in newer versions of DF. Anyone that figures out how to write a siege-generating script that works with armies having to have a target and travel overland will be a hero.
Back on the FPS topic, you can limit your fortress population and modify the invasion triggers so that all the fun enemies still show up. I do this on every game. Before world gen, modify entity_default.txt to lower all the TRIGGER tags for other entities, in particular changing to [PROGRESS_TRIGGER_POPULATION:0] and [PROGRESS_TRIGGER_POP_SIEGE:0] so you don't need large numbers of dwarves to get contact and sieges. In creature_standard.txt, for all the mega and semi-megabeasts, set [ATTACK_TRIGGER:1:0:100000], so you still have to produce things, but population won't prevent attacks. Lower the titan attack trigger in wordgen params and increase the number of titans and caves for megabeasts.
Light aquifers are extremely mild. Find a heavy aquifer if you want it to contribute to the challenge or be part of any serious water-engineering project.
As far as "impossibly hard", you have to work to make DF get truly hard, if you have well-designed defenses, since even just a raised bridge stops absolutely anything. Challenge still has to be a little bit self-imposed.
The current villains update is incomplete, which mostly means you don't have the tools to keep visitors from convincing your dwarves to give your artifacts away. I don't think there's any fix for that but to keep visitors out, so I count that as a bug more than a challenge. Intelligent undead are new, so letting worldgen run for a big and establish some necromancers to embark near will probably generate a (sadly very limited and finite) number of interesting necromancer army attacks.
Given how rare large sieges are and how they deplete attacker populations, you'll probably need to look into using dfhack to increase enemy site populations, or else the world tends to run dry and stop attacking you pretty quickly.