Screensharing slow, even over gigabit ethernet
Some (all?) Macs when run without a monitor turn off the video circuitry so they do not waste energy, even though this circuitry is used by screen sharing to dramatically speed up screen stuff.

There might be a way to turn this circuitry back on through software, but I have not foud a reliable way to do so. What works very well is to plug in something into a video port to get the Mac to think it has a monitor connected.

You can build one yourself:
https://macminicolo.net/blog/files/build-a-dummy-dongle-for-a-headless-mac-mini.html

Buy one to plug into a HDMI port on some MacMinis:
https://macminicolo.net/blog/files/an-hdmi-adapter-for-a-headless-mac-mini.html

Buy one to plug into the MiniDisplay Port:
http://eshop.macsales.com/item/NewerTech/CBLMDPHEAD/

Instructions for a resistor added directly to the video card: 
http://blog.zorinaq.com/?e=11

I picked up a handful of the HDMI ones a while back, they are very useful.

A similar question/answer is at Force the resolution on a headless mac mini server