I think you're on the right track with finding a small machine that can accept a pcie card. There are a couple decent half-height cards that can do what you want, if you're space limited.
I went with a slightly older mini-itx board that had a built in radeon 7000 series onboard and I thought it'd be good - some resolutions worked, but low dotclocks didn't or crashed the computer after a few resolution changes. These worked just fine with a proper pcie radeon 7750 in my situation. I can't accurately comment on Dolphin yet - though I did get Mega Man 9 and 10 running flawlessly in it with that card. I have to imagine for standard crt res other games would likely do fine if the processor can keep up.
I'd like to hear about people having 100% success with onboard/apu solutions but I didn't have a flawless experience, at least for Windows.