It would actually go up to 1024x768 but I didnt think the monitor looked as good like that, so I usually ran it in 800x600 instead. Of course it didnt do "HD" that buzzword wasnt invented yet, but full screen full motion video without dropping a frame it could definitely do and did many times, and 'accelerated graphics' was also something yet to come, at least in my price range.
Now I had a very special software setup to do this, of course. A 'stock' configuration on the same machine would crap itself trying to play much smaller videos, in fact I started that project as a dare because the buddy that owned that machine was complaining it was obsolete because it was performing just like you described with your pi - taking a minute to play a second or two of video - with tiny lowres files even. But the hardware was still perfectly capable of doing the job.