For internet connection, make sure you have both good download and upload speed. Usually, the upload speed is your big limitation.
For any software needed, other than Windows, I would look to opensource software, as it's free and you don't need to really worry about licensing unless you modify the code.
For office apps: OpenOffice
www.openoffice.org
For graphics: Gimp
www.gimp.org
For 3d graphics: Blender
www.blender3d.org
Web browser: Firefox
www.mozilla.org
You might also look heavily into group policies, that way you don't end up reloading your machines all the time because people delete stuff and whatnot. Remove the start button, disable shutdown, etc. There are many things you can do. You might also look into a proxy server (content filter) if you're worried about people looking at indecencies while at the cafe.
I wish you luck!