Typically the bigger UPSes will also have bigger batteries which means more run time, so I tend to oversize as much as I feel is reasonable budget wise. The 1000VA (600w actual power) are decently cheap so I usually get that, and they'll run pretty much any machine unless it's like a triple SLI type machine then you probably want a bigger UPS like 1500VA.
Never go by the run time it says on the box. That's assuming the planets are lined up properly and that Jesus Christ himself has blessed the acid that went into making the batteries. You'll get maybe 1/4 of the run time it says on the box. Typically 5-10 minutes at very most on a standard SOHO UPS at half load.