I do the initial projection from rectangular to ortho with Matthew's Map Software: http://www.users.globalnet.co.uk/~arcus/mmps/ (Linux only, unfortunately). I then use a PerlMagick script to add the labels and circles.

I am working on a new version that labels features down to 20km (16km for 2000x2000 and up), but only when the labels won't bump into other labels, so hopefully readability will not be impacted.