What OS? You could probably run Win98 if you wanted to, but to have working video drivers you'd need to stick with the earliest PCIe cards. If you install Win2K or later then you have a lot more options. There's a lot of talk on Vogons about old games that have compatibility problems with newer GPUs/drivers, so if you have a lot of older games that fall into that category then you might want something more period correct like a GeForce 7600 or other DirectX 9 level card. For more general usage or to play a newer game that would push the system's limits, you could always go with a newer card that would likely be easier to find, and with better hardware acceleration for video playback. Something like a GT220/240 or Radeon 4000 series.

I'm probably going to run Windows XP and some early Vista builds, so I'd rather go for a GPU which supports LDDM (WDDM beta in case someone doesn't know), among the PCIe GPUs supporting LDDM there are the Radeon X300, X600, X700, X800 and X850 series as well as some Nvidia ones such as the PCX series (which are rare to find and probably expensive) as well as the 6600 and 6800 series and finally the 7800 GTX (which probably costs too much and is a bit of an overkill?)

I think that the Core Solo, if we exclude the SSE3 instructions, is pretty much on pair with Dothan? If I remember correctly the best Pentium Ms running around 2 GHz were also paired with the Mobility Radeon x700, the Mobility Radeon x800 being an exclusive of a few gaming PCs vendors such as Alienware.
Although I find the lower power consumption of the X600 and the fact that there are silent versions more attractive.

Regarding Nvidia, I think that the 6 series advantage over contemporary ATI chips is the support of Shader Model 3.0? But then again I don't think that there were many games around 2005-2006 using that? And surely I could never play GTA IV with a Core Solo :')