Just to be clear - it's definitely not a resolution issue from SkyDemon. If you zoom in closely, you see the background tiles (the terrain) correctly rendered as a fairly low resolution bitmap (which proves SD isn't sending excessive data to the print driver). All the text is also vector based which is good. The issue is that the magenta line, airspaces and rivers (amongst other things) are translucent, and your driver is turning them into huge bitmaps.

What you need is either something that handles transparency correctly (PDF has been able to cope with transparency for many years), or at least lets you turn down the resolution of the internally generated bitmaps.

I've just had a poke around, it it seems the CutePDF uses the open source GhostScript library.

===
How to reduce the size of output PDF file?
You can alter the parameters used in a text file "%Program Files%\Acro Software\CutePDF Writer\PDFWrite.rsp". The key parameters are in the line:
  -dPDFSETTINGS=configuration

where configuration can be /screen, /printer, /prepress, /default.
===

Have a look here:-

http://www.cs.wisc.edu/~ghost/doc/gnu/7.05/Ps2pdf.htm

where it explains what the different options do. Try /screen and /printer

It looks like it defaults to producing 'Acrobat 3' compatible files as well which don't support transparency (this was introduced in Acrobat 5).

===
ps2pdf12 will always produce PDF 1.2 output (Acrobat 3-and-later compatible).
ps2pdf13 will always produce PDF 1.3 output (Acrobat 4-and-later compatible).
ps2pdf14 will always produce PDF 1.4 output (Acrobat 5-and-later compatible).
ps2pdf per se currently produces PDF 1.2 output (Acrobat 3-and-later compatible). However, this may change in the future. If you care about the compatibility level of the output, use ps2pdf12, ps2pdf13, or ps2pdf14, or use the -dCompatibilityLevel=1.x switch in the command line.
===

I don't know how you'd encourage CutePDF to use ps2pdf14 - perhaps contact their support folks?

It may be as simple as adding: -dCompatibilityLevel=1.4 to the above config file, or they may expose it in the GUI somewhere.

This looked very promising.

Unfortunately, CutePDF has already set -dCompatibilityLevel=1.4 in its parameter file by default.

I tried to play a bit with the -dPDFSETTINGS= setting to create various output files from SkyDemon, but it made no difference.

If that setting is making no difference then something is wrong. It should materially and significantly affect the size of the resulting PDF file.

I'd suggest contacting their support folks.