Hi,
I bought my first lcd tv (samsung 26") for my uni bedroom a year and a half ago, and found the picture quality depressing at first. I thought freeview (and even dvd) looked rubbish. I bought an upscaling dvd player which made things better. My xbox looks great, and sky looks pretty good too. You may just be suffering from the initial switch over from crt to lcd, but if this is the case you'll get used to it.
I don't have sky hd, but i have seen bbc hd in shops and it looks good, so i expect upgrading sky to hd would make things better. Unless ofcourse your tv has a problem in which case disregard everything i've said above. I haven't seen your tv but i imagine it's better than my old 26" samsung.