I used the jetway boards / daughter cards that Chris mentioned with success for various projects from the built-in control, my home router, my HTPC interface.
You did not indicate what the actual application is, but if you need something more industrial due to temperature or humidity limitations, I found http://www.logicsupply.com/ to be a good resource for mini X systems, who can beat.
The tip for this board is that, given the minimum storage requirements, do not use a hard drive. Use the IDE adapter for a compact flash card as a system storage or SD card. No moving parts are usually a big plus in these applications. They also usually offer DC powered models, so you can use an external power source for your laptop or wall, which minimizes its final size.
This http://www.fit-pc.com/web/ is another option on the very small PC market with atoms, you will probably have to use some USB converters to get the desired connectivity.
The Beagle recommendation mentioned by Paul is also a good choice, there are daughter cards for this that add all the ports you need, and you have a built-in SD card reader for any storage you need. It is also significantly lower power compared to atomic systems.
There are a ton of single-board computers that fit your needs. When searching, you usually find that they do not contain many interface connectors on the processor board itself, but you need to look at the daughter cards in the stack that will provide any connections you need (RS-232, etc.). Often why you see only the “serial port” in the description, since the final physical layer for the serial port will be defined on the child card.
There are a ton of hand-based gaming platforms that you can also use, for many that are listed, they look like a beagle board. Googling for "System on module" is a good way to find many options. They also usually represent a module with a processor / plunger / flash on 1 card, and then offer various carrier cards to which the module is connected, in which various forms of connection that you need will be provided.
From a developmental point of view, atomic boards are likely to be the lightest if you're more familiar with x86 development. ARM is heavily supported on Linux, although it's not that difficult to work with.
Personally, I would avoid windows for headless design, as you discuss, I rarely see a Windows-based embedded device that is not just bad.