Converting from electric baseboard to.......????

Vermonter_2

Here's the scenario:

You just got a call from somebody in southern Vermont. The house is mid 60's and heated with electric baseboard throughout. It is about 2,600 sq.ft. on two floors. The house is built facing west on a fairly steep grade. Elevation is roughly 700ft. The lower level is pretty darn cold since so much of it is below grade and it feels like there is little insulation between the slab and cinder-block walls and the earth it's buried in. The second floor is warmer and has a wood burning stove that keeps things comfortable even in the bitter cold. In the afternoon there is major solar gain due to the amount of glass on the west wall.

Any suggestions as far as what to replace the electric baseboards with? I'm leaving this pretty open because I already have a few ideas but don't want them to exclude other approaches that may be totally different than what I'm thinking about.

Thanks!