What are you planning on using the relays for?
I have found that the Dallas DS18S20 and DS18B20 temperature sensors are close to my other thermometers (I have two Vernier "GoTemp!" probes attached to the same machine, sitting side-by-side with two of my Dallas sensors), but they can be off by a few degrees.
I have a 4-pack of the DHT-11's on order (from a Chinese seller on eBay, of course). I want to see how they compare in terms of accuracy, as well as use them to track humidity in the house.
I think you'll find the Arduino pretty simple to use, once you get started. Once I had everything working on a breadboard, I bought a prototyping shield, and soldered it up. That was the hardest part for me. I've been soldering stuff for many years (as the son of an EE, I was taught how to do it early on), but I didn't really have any experience soldering on perfboard (I usually asked my dad to do that part).
In addition to soldering up the shield (during which I made one mistake - I switched the input and output pins, so I had to fix that in the software), I also soldered up the board for the thermostat interface.
My program in the Arduino is pretty basic (since I'm not a programmer, either).
It checks the status of the three thermostat lines (pulled low with a resistor if off, or pulled high by the relay if on). It then turns on or off the appropriate LED for each one (I did the LEDs in the program, mainly so I could see if it was properly detecting the Thermostat cycles - and I liked it enough to keep it that way). Next, it polls the six temperature sensors. It then outputs all the data in CSV format via the serial port. It loops every 10 seconds (or so).
On the PC side, I'm using RealTerm to capture the data to CSV, adding a time stamp at the beginning of the line. I use the DyGraphs Javascript graphing engine to display the data. I'm working on a data logger that will go to a database, but I'm not there yet.