Most UPSes won't help unless they're online UPSes.
You need either an online UPS (one which runs in UPS mode at all times--which means you will want a pure since-wave one! And they are mighty expensive) or you will need a really good power filtering solution. None of that monster cables crap, but a good power filter. I'm sure APC has something. Not going to be cheap, though. Expect to spend in the hundreds of dollars.
Or save money and get an electrician to fish you some new power straight from the panel.
This is an example of the sort of device I'm talking about:
Generally, they will have huge chokes in them, possibly even an autotransformer. This makes them very big, heavy, and expensive. But they will make the power clean again. You can UPS if you like. An online UPS works as a power conditioner simply because it is ALWAYS providing battery based (generated) power so you are completely disconnected from line power at all times--and the batteries don't care as much about dirty power.