Ok, a list of must get is needed:

Shooter - Killzone 2, most gorgeous shooter, only to be topped by KZ3

Action RPG - Demon Souls, old school dungeon crawling, expect to die and learn from the mistake

Stealth game - MGS 4, best stealth game ever

Strategy RPG - Valkyria Chronicles & Disgaea 3, VC has beautiful and touching story, and Disgaea series is the ultimate SRPG with ENDLESS customization

Game as art - Flower, to save the earth

Platforming - Little Big Planet, create ur own game

Action Adventure - Uncharted 1 & 2, romance and adventure

Hack & Slash - God of War 3 and Collection, its God of War

Racer - Wipeout HD, 1080P seizure causing high speed racer, free 3D update on the way

Horror - Siren New Translation - scariest game ever, made by original creator of Silent Hill

Motion gaming RPG - Folklore - one of a kind, the only game that Six axis motion to trap monsters and for summoning, with beautiful haunting landscape and creatures

JRPG - FFXIII???, nah, u got 1080p video and 720p gameplay vs 360 version alright, but the game is too much of a yawn. still no decent JRPG yet

Buy demon souls... the game may be the hardest game this generation have seen yet but when you actually finish a level
after dying 50 times , it actually feels satisfying. Be warned though the game may take a long time to finish took me 60 hours.
oh and the game is not open-ended you are basically travelling in worlds which are connected by a central hub.
every world has a level (like mario world 1-1) and every level has a boss.
Theres a unique multiplayer aspect in the game where you can write messages
to help other people playing the same level and there's co-op and PvP too xD
you definitely should check the game out.
actually theres so much things in the game that its hard for me to explain everything here sorry =(

Really? Does the memory and PSN games take up a lot of space or something? I've actually had a 20 gig HDD for my 360 basically since launch and have had little problems with space. Had to clean out a bunch of game demos but nothing too serious..

Maybe I should opt for the 80 gig model then.. It's a little bit pricier on amazon, but only about 15 bucks more so should be worth it.

Haven't gotten it yet actually so I still got time to make up my mind on which model, I'm waiting on my earnings from a bunch of old games I sold on amazon to transfer to my account then I'm going to buy it.

don't know about you but MGS4 is far from the best Stealth game ever , its not very stealth based like the older games.

as for Siren , its also far from being the scariest , though I HUGELY recommend this game ,its the FUNNEST horror game this gen , but not scariest, it have a very unique gameplay and there is no main character in it , its intense.

as for JRPGs i'd reccomend White Knight Chronicles! , also LIKE EVERYONE DOES you forgot the best game out there and that is YAKUZA 3!!!

A joy to see that people are still playing  Folklore and recommend it.

the problem with PS3 games is that the older games need installation you see? so they take up space, 80 GB is fine as a start.

also PSN Games are limitless so some games are huge (like siren which is 1.2 GB each episode) and some of them are "minis" which is less than 100 mb

plus most games need updating as well , so that extra space is needed, i don't know about Bluray movies but they might need installing as well, not sure.

I know it's being recommended a lot, but I'd actualy recommend skipping Killzone 2, as much as I hate to say it. LBP and Demon's Souls alone will give you 200+ hours of content to run through, and between those two, SMG2, and all the other games coming this year, you might as well just wait until Killzone 3 drops next year, as it seems to be fixing every small complaint people had with Killzone 2. It's not like you'll be missing much story-wise anyhow (the weak narrative was my biggest issue with KZ2).

i would recommend:

 Full retail games: 

 Resistance: Fall of Man
 Resistance 2
 Ratchet and Clank: Tools of Destruction
 Ratchet and Clank: A Crack In Time
 Metal Gear Solid 4: Guns of the Patriots
 White Knight Chronicles
 Valkyria Chronicles
 Uncharted: Drake's Fortune
 Uncharted 2: Among Thieves
 Demon Souls
 God of War 3
 Gran Turismo 5: Prologue (might be worth waiting for Gran Turismo 5 though)
 Heavenly Sword
 3D dot game heroes
 Infamous 

 PSN games:

 Super Stardust HD
 Burn! Zombie Burn!
 PixelJunk Monsters
 PixelJunk Eden
 PixelJunk Shooter
 Fat Princess 

 Also as others have said -- get a bigger HDD as some games have mandatory installs ranging from a few mb to 5gb. Any 2.5" HDD will work.

I'm rockin' a launch 60gb, and I've still got 17gbs of free space.

@metallicube:  If you're going to be buying mostly exclusives for this thing, I wouldn't worry much about installs.  Almost all of Sony's titles have no installs.  The only two I can think of with significant installs are HSG5 and GT5:P, and the latter only because you basically install the entire game (for those who didn't want to buy it on PSN).  Killzone, Uncharted, Demon's Souls, etc. have no installs.  LBP has a decent sized cache, but that's it.

It's mostly Capcom and a few others that force you to install games.  And MGS4.

congratulation
and yeah you need bigger HDD, most of the games need install , eg. mgs4 needs 4gig but on average most games need 1 gig so go for 80 gig in my opinion

i wanna recommend a bluray set, buy Planet Earth it is a master piece , this set shows you the advantage of having bluray player trust me

as far as games go:
lbp is a must buy,
GowIII . heavy rain, killzone 2, uncharted2, and 3d dot games are good games

psn games:
flower, critic crunch, Digger HD. superdust HD, fatprincess, pixeljunk monster, and mushroom wars