Alkaline D-cells are the highest capacity primary cells that are readily available. Any number of them can be connected in parallel for increased lifetime. The only risk is failure mechanisms; if one develops a short circuit, it will discharge the entire pack. Thus you want to use top quality cells, preferably all from the same production run. Check out the following site for more details:
http://batteryuniversity.com/learn/article/serial_and_parallel_battery_configurations
For the high voltage, AA cells are usually the most cost-effective source, and 24 of them in series will provide 36 volts for a long time. The site above has more detailed information on series connections as well.
Rechargeable cells are more cost effective over the long run, but they usually have so much self-discharge that you can't get a longer life by using more or larger cells. A good idea if the Quickie is running 12 hours a day, but in normal home use you still have to charge them every few months.
Hope that helps!