I'll say that first and foremost, the lamps are very unlikely to be your problem. If it really is an issue on the lamp end, your bulbs may be going bad. Do they both flicker at the same time? If so, given that it's summer (assuming you live in the Northern Hemisphere, that is) and everyone is running their air-conditioners, it's probably just the power company struggling to meet demand and has nothing to do with the lamps or bulbs. You might try turning off your own AC and seeing if that changes anything, as unbearable as it may be to work in the heat. Otherwise, you could test a different surge-protector.

If they flicker around the same time, I would definitely say it sounds more like a power supply problem than a bulb problem. Before you buy bulbs, try letting one lamp run straight from the wall and see if it still flickers, just to make sure it isn't the power-bar.

EDIT: It just occurred to me that we're probably using bulb and lamp interchangeably- I was thinking that you meant the fixture when you said lamp, so that's my bad. If you happen to use fluorescent bulbs, there are a few problems that could cause flickering, one of which is cold. You could watch and see if they do it less once they've warmed up a bit.