http://www.us.playstation.com/Support/CompatibleStatus
Here’s a resource from Sony regarding title compatibility. From here on out, PS3 won’t be backwards compatible. If you got an 80GB, you’ll have to check the model number. The Metal Gear bundle fetches a premium because they are compatible.
I’ll second the suggestions made already, though most of them require some platform jumping that might frustrate you (since the couple spots in Shadow of the Colossus and Psychonauts I had trouble with come right near the end of the game, it made it doubly irritating) but they are so great otherwise, I would still recommend them. Beyond G&E 2 is in the works for PS3, finally.
If you can get more into traditional RPGs, Disgaia 3 is a PS3 exclusive that is pretty deep. The graphics are bad, but the mechanics are complex and require a decent amount of strategy. Like Psychonauts, it has a warped sense of humor.
Fallout 3 is another I might suggest renting if you’re worried about the combat. You can play it as an action game or pause it and choose your combat actions. The real heart of it though, is an extremely immersive world with lots of wandering around exploring quietly, and complex moral dilemmas that let you decide how to resolve them.
Valkyria Chronicles just came out and is really fun. Once again though, more RPG battlefield tactics opposed to pure puzzle solving.
If your PS3 is backwards compatible, I’ll dig through my boxes of PS2 games and try to come up with something closer to Myst, but there’s not really too much of the explore at your leisure style on the consoles.
I know you just got a PS3, but the DS experienced a revival of exactly the type of puzzle game you’re asking about. There are lots, some better than others.
HEAVY RAIN is one to keep in mind, it’s not out yet (sometime this year), but the company’s other games were heavily puzzle and moral decision based. Dragon Age is coming to PS3 for Christmas this year, but it should be excellent. Brutal Legend is from the makers of Psychonauts and will also becoming later this year.