I had the same problem when I bought an LCD HDTV (though a Plasma may have worked a little better) last year and tried to hook up my old school consoles up to it (PS, Saturn, Dreamcast, PS2).
After about a month of research trying to figure out why my games looked worse on my new TV, I learned that most old-school game systems (and the games for them) output a resolution of 240p or 480i. Since HDTV's are designed to display higher resolutions of 720p, 1080i or 1080p, it causes the older games to look worse because the HDTV has to "de-interlace" the low-resolution signal coming from the games to fit the high resolution of the HDTV. Most HDTV's apparently can not do this very well plus some introduce controller lag issues as well because of the poor de-interlacing.
My solution was to get a smaller LCD HDTV for the consoles that do 480p (Dreamcast, XBox) or higher (360 and PS3 if I can ever afford it), a regular CRT for the older consoles and use the rest of the money to invest in a front projector.
My primary goal was to get a gaming display device that I could use for my old-school systems, that saved a lot of space my CRT was taking up, give me a pretty decent sized screen and be HD so I could get the benefit of the newer consoles. I thought the LCD was going to do all of that for me but it didn't so I have to use two displays for the time being. From what I have been reading on this site though (in the sub 3K forums), a front projector might accomplish what I want. The money I was going to spend on a 50" HDTV I put towards my 2 set solution and still have money left over to try out the projector idea. The sound system, screen and bulb warranty I will need to go along with the projector is making me have to save a little bit more though.
There were some other solutions I found out about that might work for you though:
1) An "upscan converter" (the term may be incorrect) like the XRGB series Micomsoft (not Microsoft). They are pretty scarce and expensive but from reviews I have read on the web, it accomplishes exactly what I wanted for HDTV's. Basically it takes the 480i (interlaced) signal from a game system using an RGB cable (better than Composite or S-video and on par with Component) with a SCART connector (only used in Japan and Europe) and allows you to see your display on a computer monitor (or HDTV). They originally sold for like $200-$300 but were only produced in limited quantities in Japan. I couldn't seem to find one anywhere when I was looking and even if I did it was too expensive for me to test. From reviewers though, it was definitely worth the price though as compared to the picture quality of cheaper VGA boxes. Ebay has had some occasionally though.
2) You could also try an external scaler/upscaler/de-interlacer or an A/V receiver that does this. I tried researching some but found that they are generally pretty expensive because they are basically designed for people with HDTV's who want the quality of regular TV and DVD's to be on par with their HD content. There may be a reasonably priced option that I haven't heard about before though.
3) You could try running the consoles through a PC and then to the HDTV using one of those capture cards that let you watch TV on your computer. The computer would have to upscan the resolution from the games to display it on the monitor and you could just send the signal to the HDTV as well. I have a two-year old laptop so my assumption was that there may be lag issues but if you have a desktop or gaming PC, it might do the trick.
Anyway, this is a long reply and probably more information than you needed but I just wanted to share the fruits of my struggles since I was in the same boat as you a few months ago. As you can tell I am in no ways an expert but have been researching a lot because of my bad experience with the LCD. Always good to meet a fellow retro gamer. Wish I had more time to play.
If you find a better solution please let me know. Someone else may know of HDTV's now that do a better job of de-interlacing internally.