Piece of cake. Since you'll have the EIA232 interface for remote programming I'll keep the user interface for the thermostat itself simple. Microcontroller shopping list:
- UART
- I2C and/or SPI
- 2k or 4k Flash
- around 16 digital I/O, able of 20 mA drive
High speed isn't required; 1 MHz or so is enough. Plenty of microcontrollers will fit this picture, like for instance the AVR ATtiny48 to name one. Available in a DIL package, may be a plus.
This is what the display could look like:
You probably don't need 4 digits, for 3 digits you need 11 I/Os.
For the temperature sensor you could use one with digital interface, SPI or I2C, or analog; the ATtiny48 has ADC. I2C needs 2 wires, versus 4 for SPI, and I2C has the advantage that it's a bus, where you can connect more than 1 sensor if required. The TCN75A also mentioned by dadinck is suitable: a 2°C accuracy, and you can connect 8 of them to your bus.
That's 2 I/O pins.
The UART will only need TX and RX, that's 2 pins, which interface to a MAX3232 or similar transceiver.
The RTC can be an I2C device, so we hook that up on the bus. Let's use a PCF8563 for that.
The ATtiny48 only has 64 bytes of EEPROM on board, and that may or may not be enough to store the thermostat program. You'll need 3 bytes per switching moment: 11 bits for time of day (9 bits if a 5 minute resolution is enough), 7 bits for days of the week, and 5 or so to store the temperature for that time. With the internal EEPROM you can store 21 switching moments, but then there's only 1 byte left for other settings (whatever they might be). Anyway, if you need more EEPROM, again we'll use an I2C device, like the AT24C04B. 512 bytes and only 28 cent.
We've used 15 I/Os so far, and we'll obviously need one to switch the heating through a relay. That's 16. The ATtiny48 in DIL has 23 I/Os available, so there are a few left for buttons/switches. You'll want at least a on-program-off switch.
The ATtiny48 has an internal oscillator which can be calibrated to 1 % accuracy. (Personally I would have preferred that Atmel did this in production.)
The 4 kB Flash should leave you enough spare memory to include a flight simulator, so to speak.
That's a basic setup with an AVR. You can do the same with a PIC or any other 8-bit controller for a comparable price.
The power supply can be a compact module like this one:

More compact and efficient that the classic linear regulator.