Definitely go with micro ATX. Aside from that, decide on your software first and build your hardware around it. There's nothing more frustrating than having a great piece of software that doesn't work properly with the hardware you've built.
For tuners, go for one that does hardware encoding. That'll take a lot of the load off the CPU, and it'll allow you to have multiple tuners encoding at once.
Torifile's suggestion is interesting, but that won't allow you the expansion to have more tuners that a home-built box will. Start with a micro ATX machine, and if you decide you need to add more tuners than your board can handle, just buy a new case and motherboard that are compatible with all your existing stuff. Plus, with the mini, you're basically limited to USB tuners, and the options are just not as good.
For software, Windows Media Center is pretty decent. I'm not sure what editions of Vista it's included in, but you should probably be able to find XP MCE at NewEgg.com still.
When I had a Windows PVR box, I was using
Media Portal. It's not as robust as Windows Media Center, but it is free. If you've got a spare XP disc laying around, you might want to try it out. Even though you can't record, you can still play around with the other features of the interface to see if you like it.