What are some ways to improve a voltage multiplier?
You need to ditch Rd from your first schematic, and use a low impedance push-pull output as in your second schematic. However, as you correctly say, 36v will toast the gates of 20v Vgs FETs. There are few fets with Vgsmax greater than 20v, and none to my knowledge with more than 30v.

Amongst the options are to use 

a) suitable level shifters to control the FET gates, small bipolars would work well here
b) a gate drive transformer (though usually only used for higher power applications)
c) how about 18v push-pull drive from two batteries, but in push-pull, like this ...







simulate this circuit &ndash; Schematic created using CircuitLab

I've illustrated 4 stages here, the extension to more stages is obvious.

Now, I've not connected the upper capacitor. There are two options

a) Cockcroft Walton stylee, where you are limited by maximum voltage. Here, you'd connect C5 to the D1/D2 junction. This allows low voltage across each capacitor, but results in high output impedance. Also known as a Villard cascade, though invented by Greinacher.

b) Dickson charge pump stylee, which results in a much lower output impedance. C5 connects back to the driven end of C2. This means C5 needs a higher voltage rating, but if you can get caps with a suitable voltage rating cheaply, 250v or even 400v are commonly available, then this configuration has a much lower voltage droop with current.