Well even when I deleted everything from my good old 40gb Ps3, I couldn't download Hitman Absolution or  Kingdoms of amalur reckoning from PSN..Even if they are 14-18gb games, says its not enough.Both are games I really wanted to play but now I either have to buy disc version or somehow try to upgrade my hardware (and I'm not sure how).

Just annoying...Oh and "new" PSN is slow as hell at least on my console

Did you delete (physical) game installs as well? That's what takes up most space on my ps3.

How much space does your ps3 say is free?

the fat model has a HDD slot at the bottom side - just buy any 2.5'' (notebook) HDD

here is one of the hundreds of youtube videos on how to do it (I only clicked through it, but I assume it covers all the important points from what I saw): https://www.youtube.com/watch?v=BxzyPrrkJPs

and yea, the PSN store for PS3 is really slow, I hope they improve that alot for PS4, but you can access it through PC here: https://store.sonyentertainmentnetwork.com/

I subbed to Plus a few days ago and so came across the same problem as you with my fat 3. I just bought a new 500GB hard drive for laptops for cheap and plugged it into the PS3. Now I have Hitman Abs, Catherine, Dead or Alive 5, Kingdoms of Amalur, Shadow of Collosus, Ico, Demon's Soul, Malicious, Lord of Rings War of North, Cave, Motostorm Apocalypse, Infamous 2 and LBP 2. All this and I still have tons of space to spare for the upcoming months.

God I love PS Plus. There is literally an overload of games. Best...Service...EVAR!

I can't believe you get an entire year's worth of about 40 of these games for the price of one game. And I don't even have a Vita to access the Vita games. Crazy.

As others have said. 40GB is just not a viable option when you want to fully embrace PS+.

Best option would be to upgrade to a 500GB 2,5" HDD, if that would be too expensive, well then the biggest 2,5" HDD you can afford. Cheers and enjoy PS+!

Your HDD is ancient , it is slow because it is full, and its slow because it is old, you should really replace it, you should get AT LEAST 500 GB or convert to SSD (much much faster than HDD, though kind of a waste using it on PS3) , you can get a 1 TB HDD for about the same price as a game nowadays so get one.

upgrade to a 500gb drive

If you have a PS3 with less than 160GB, you are doing it so very wrong.

Anyway, if you really want to play one of them, delete everything on your HDD so you have at least 28GB of space, then you can download whatever one is 14GB. If you want the 18GB game, you will need 36GB, which I doubt your PS3 will be able to do.

I suggest you do this with Hitman first as its about to expire.

I've come across a similar problem since I have PS+. You get just so many fantastic games for free that you will fill up an ancient, small HDD in no time. But as others have pointed out, installing a new and bigger HDD is a very cheap and simple process. Just buy any 2,5" SATA HDD and replace the old one. Not only will any storage space related problem disappear, new HDDs are also much faster than ancient ones. You could buy a 2,5 SATA SSD as well, they are just insanely fast, but they are also extremely expensive compared to standard HDDs. If you want the best of both worlds, get a hybrid: a HDD with an SSD cache.
Here's some prices:
- 500GB HDDs start at about 40 Euros
- 1000GB HDDs start at about 57 Euros
- 500GB HDD+SSD hybrids start at about 62 Euros

Drives with less than 500GB don't make much sense nowadays, as you will save hardly any money.

Just upgrade the HDD. I bought a 500gb one for my 120gb slim model and still have over 200gb free (even though I've only had + for about 9 months)