Note that if bandwidth isn't an issue for you, you might want to consider PlayStation Plus.
InFamous 2 is among the free games on offer. You better move on it as they frequently rotate out the free games.
Here's one of the best deals you will find on a subscription - R365 for a year:
http://www.btgames.co.za/bt/infopage.asp?C13702
I wouldn't bother with Killzone 1 and 2 unless you are planning to become a franchise fan or something. Killzone 3 is the best one in terms of graphics and gameplay. They are pretty generic shooters.
If you are looking for a good shooter on PS3, also check out Resistance 3 - great story and gameplay in that one.
The Uncharted series never really captured my attention. Story-driven action-adventure 3rd-person shooter with an modern-day Inidana Jones vibe. The series is highly praised because it broke ground in terms of visuals, and also had pretty slick design. Plenty of spectacular set-pieces - press X to win! Underneath the impressive veneer it's a fairly generic 3rd person cover shooter with some linear platforming elements.
Again, in this case go for Uncharted 3 as it's the best in the series and has been enjoying regular updates and multiplayer support.
InFamous is probably your best bet if you want to get into a series (there are only 2 games released so far). Your decisions from InFamous 1 will carry over into InFamous 2, but don't think it will be all that significant. It's a nice touch but doesn't really affect InFamous 2 that greatly.
You'll be seeing a pattern to my advice by now - go for InFamous 2 and skip 1. They ironed out some of the design flaws from 1 while retaining what made it good. Of all the games mentioned you'll probably get the most longevity out of InFamous 2 as it's pretty massive. Also, it has a nifty feature of community designed and shared missions that can be injected into your play experience, so it's a pretty robust game.
Finally, if you enjoyed God of War I'd like to throw in a suggestion for one of my favourite games - Dante's Inferno.
Good luck!