According to some of the smarter forum members over at GAF, this is an issue with the PS2 inside the PS3 not having the correct software scaler. Based on that assumption, and since I just picked up a PS3 last night, I decided to try some things out.Backwards Compatibility Issue & Partial Fix
Since the HDTV Xploder disk for PS2 is a way of "grabbing" the scaler in the PS2 you can use the disk to boot some of the troublesome PS2 games. Regardless of what you do, I recommend setting the PS3's display to 480i only. Haven't done any updates yet, but on my PS3 you can go into the custom video settings and uncheck everything except 480i. This theoretically gives you a more native signal from the internal PS2. If your game supports 480p just select the option in the PS2 game not within the PS3(We don't want the PS3 handling the PS2's display).
What the above does is lets you use the HDTVX disk for troublesome games which is mainly the ones that do not support 480p. Most of the games I tested that do support 480p seem to look fine. It is mainly the games that aren't displaying in a native 640x480 resolution that often give trouble.
Valkyrie Profile 2 looks perfect in 480p 16:9 without the boot disk
Final Fantasy XII looks terrible in 480i 16:9, but looks gorgeous via boot disk in 480p 4:3
(16:9 isn't available in 480p for FFXII)
Silent Hill 3 looks crap in 480i, but looks fantastic in 480p via the HDTVX disk.
All Sony needs to do is put the scaler software that Xploder is using for thier boot disk and add the options to select 4:3 or 16:9 and 480i. Stick that in the PS3 via firmware update and everyone is happy.