If you're planning on getting a mobo with onboard video, the only possible choice for gaming would be an nForce micro-atx board. If you're playing any games made in the last few years you will want to use a 3rd party video card rather than the integrated one.
With that said, are you looking at an AMD or Intel based system? There are a few flex-atx (super small) motherboards out there but more than likely you will end up with a micro-atx motherboard and a micro-atx case. If you go the AMD route (or even if you go Intel) it's probably a good idea to find a micro-atx case that can fit a standard ATX power supply...Many of them do this but you should make sure of that fact before purchasing one. Check out
www.directron.com micro-atx case selection and see if those sizes fit with what you're looking for. If those are still too big then your options start to get more limited without going for an overpriced laptop.
Now if you want to go super small, check out Shuttle's SV24 snazzy little PC. It can take a P3 or Celeron (though not the newest ones) and has 1 PCI slot. Everything else is totally integrated and the price includes the case, power supply, special heatsink/fan, onboard sound, LAN, firewire, video, etc. It's a great product but the performance might be a little low especially with the onboard video in games.
Gaidin