Ungrounded outlets, what are my options?
This is a good question which can have a variety of answers depending on the exact case. I would open up the breaker panel and see if there is a ground running to it. It is very possible that the breaker panel is grounded and that the neutral is grounded but the outlets and lights aren't. If you don't know how to tell if the panel is grounded, you could take a picture of the panel and post it here and I'll edit my answer.  Many surge protectors don't work at all if they aren't properly grounded, and those that do are much less effective. When you moved in, were the outlets two prong outlets or three prong outlets? If they were two prong outlets then you can't upgrade them to three prong without making sure the whole system is grounded properly. If they were three prong outlets when you got there then you Landlord is liable and he must get it fixed. Ungrounded three prong outlets are a real hazard.

In any case, I would try to find out what is really going on and then approach your Landlord. Since you don't own the house, it is neither your responsibility nor your right to do anything major without approval from the landlord and in this case since it could is a safety issue, and it is definitely an upgrade on his house, your landlord should pay for it... or at least pitch in.

No, a GFCI will not fix the problem. A GFCI does meet code [210-7(d)(3)] and is better than nothing but it is a last resort.  It is my belief that it only satisfies the NEC because they knew that some people would not do it right and they figured that the GFCI outlet was better than nothing.

Edit after Your Uptdate

You may want to make sure that they didn't use any "bootleg grounds." Those testers are easily tricked by these false grounds but these "tricks" are not safe.