The problem with the Quake skies as you said is the sphere, so it looks like you are on a floating island.
The first way i kinda get around this is by making the cliff so high that it looks like you are above the clouds when you look down, which helps the illusion a bit
The other way is like you did with the towers in your map, I stick things out of the immediate area as "skybox" decoration. Q3 and HL2 have the best skyboxes because they support sky portals, which let you use real geometry as skybox detail so it looks like those mountains are really there, but Hexen 2 can't do that so you have to add things in the actual level to mask it.
Your cliffs look like they help a lot, but you could probably even take it one step further and add slightly smaller structures behind them, or do things like place a statue with a "scale" value of 0.5 and stuff like that to produce the illusion of size
Also if i were you i'd turn off multitexturing in video options and set r_skyalpha to 0.3, looks much nicer IMO