You should get something like an ATI 4xxx. You will need a PCIe slot (not AGP).
The newer cards have the advantage of hardware decoders to offload the task from the CPU. For example, a BluRay rip of Hellboy 2 @ 1080p (MKV, AVC) dropped from 65% CPU load using an X2-4800+ AMD to 3% (yep, THREE PERCENT!).
The easiest way to use these hardware decoders is to install K-Lite Codec Pack (Standard or Full). Use the included Windows Media Player Classic Home Cinema (WMPC-HC); you need to enable DXVA in setup or after in the Options.
Again, look for a newer card that has H.264/AVC, VC-1 and MPEG2 hardware decoding (aka "UVD").
How powerful?
This dependson the following:
1) Budget
2) Power Supply
3) Purpose (gaming?)
4) CPU
For example, an X2-4800+ CPU can use up to about an HD4850 at which point most games are limited by the CPU.
All modern cards are pretty much identical for Windows multi-tasking. It only really matters for gaming (and connectivity such as HDMI).
I recommend at HD4350 256MB or higher ATI HD4xxx.