Thank you for the replies. The moral is get the displays off of the arduino 5V line. I am currently using a 9V/1A wall wart plugged into the barrel jack of the mega, and the 5V pin in the header is powering everything.
I am inferring what CrossRoads was getting at was to use the external power supply to not only drive the mega, but also the displays. The documentation for the mega mentions that when using an external power supply through the barrel jack, you can access the unregulated voltage through Vin on the mega. Can I use this to drive the displays, using a voltage divider to step the 9V down to about 5V, which is in the input voltage range for the displays?
BTW, the DS18B20 is inappropriate for this application. I need real "probes", capable of penetrating whatever I am cooking, and all wiring needs to be heat resistant, not to mention the temperature range of the DS18B20 is not large enough. I considered thermocouple probes and amplifiers, but this would increase the cost by about 7x.