As far as I know, in Internet Cafes, Windows XP is the most sought after OS.
Vista is as big a headache as Linux to configure and maintain for a newbie, remember that. I have used both as a newbie, and I found Ubuntu to actually be EASIER than vista, while I come from a Windows XP background.
As far as using linux in an internet cafe is concerned, I suggest it if and only if you have a good ability to learn and pick up new knowledge. Once you manage to set it up, you can do several things, like block certain programs, disable customer from downloading large files, etc. You can also setup a server which acts as a proxy with a common cache along with filters to speed up internet.
Getting the end user to use linux on the other hand is a fairly straightforward procedure.
I suggest xfce for this. Just create shortcuts to all commonly used applications on desktop. Keep firefox as the browser and apply some nice looking theme like noia 2.0, along with extentions like adblockplus to attract customers. And use a pic of windows XP's start menu button as the button for Xfce menu. It would look hardly any different from windows XP and most people will use it normally.
OR, even better, use XPDE, a windows XP interface clone for Linux. DO the same things - Keeping all app icons on desktop.
You have some really light weight and addictive games like Urban Terror for Linux. I suggest you set this game up and enable people to play it over LAN. It works on weakest of systems, and customers will enjoy it.
I suggest you have windows XP (and not vista) on ONE computer, if the users have some programs to execute.
As far as system configuration is concerned, whatever you do, have atleast 512MB of RAM. Linux can't run well in lesser RAM. For CPU, even an old 1.7GHz Pentium III or Athlon XP will do on your client machines (have good hardware for machine running windows xp and better hardware for your main server, the computer which you will use).
For software, on both windows and linux, you can have OpenOffice.org 3.0. Its almost exactly like MS Office, and users will have no problem adjusting with that.