LCD Resolution and User Complaints

My company is starting to replace CRT monitors with flat-panel LCDs. The LCDs have an optimal resolution of 1440×900 which gives a sharp image but small fonts. If the resolution is set lower the image is stretched out and looks fuzzy. Unfortunately, our users do not like either situation and we, the IT department, are getting several complaints.

Do any of you have similar experiences and what settings changes or work-arounds have you tried?