Here is a nice Shuttle. Getting a cheap video card probably wouldn't hurt anyway. Especially in that one since it doesn't come with onboard video.
I wouldn't go with SFF if I were you, even though they are cool. Just go with a stable motherboard, and if it doesn't have onboard video just pick up a cheap card.
It's a good thing they give you a power supply because it would be hard finding one that fits. Those things probably overheat like crazy though, the whole inside I mean.