TiNman and EIB are right, you should tell us (well, them
) the formats and video containers you're looking at watching.
That said, here's a "bigger" question: why bother?
First, the guy at Future Shop's an idiot: lots of videos work on netbooks.
Next, as ThisIsNot pointed out, a lot of HD downloads aren't really HD. Here's where my "why bother" comes in--there's no reason you *have* to watch an HD-quality download on a netbook. Most screens are so small the HD clarity isn't really a selling point, IMO. (Of course, your mileage may vary, ThisIsNot here is an admitted video junkie).
I'd expect most of your downloads to work fine on notebooks already out. I suspect the biggest issue won't be clarity, but might be speed and the possibility of the video "skipping." That could be an issue, and I'd suspect you're looking at Windows netbooks, so I can't help there, but I'm running linux (xandros) on an EEE PC with 512MB of RAM. Running AVI files (h264 and other codecs) or DivX files from a portable HD or from the SD card have had minimal skipping issues (none for the AVIs, only large DivX files have caused skips).
The folks here will be happy to confirm with further information from you, as you can tell the community here is great, but that said, I would suggest with some confidence that you will probably have no issues (except, perhaps, with the frustrations of Windows 7 Starter)