Can the Pic Vss be connected to the minus side of the +55 to+75V supply?
The Pic A/D converter can strapped to be ratiometric w.r.t. it's own Vdd, or it can be fed from an external reference. You have two options: regulate the PIC's Vdd to sufficient accuracy, or dont worry about the exact PIC Vdd, and buy a voltage reference chip.
As to the efficiency question, use a "buck" switcher. Look at National's or Linear Technology's chip solutions, or buy a ready made one. Any decent switcher will have an efficiency of at least 85%.