If you want high accuracy and resolution, I think you had best use a sensor module, such as the SHT75 you refer to. If 0.5C accuracy and resolution is sufficient, then the Dallas DS18B20 is an inexpensive choice.
Another possibility is the LM34, which if used with the Arduino's 10-bit ADC with Aref connected to a precision 2.5V bandgap reference (LT1019) will give you 0.24 degF resolution and uncalibrated accuracy of about 1degF or better.