Distro wise, it really depends on what you want to do. If your requirements are down the server road then I highly suggest that you use CentOS. CentOS is the favoured distro of many webhosts (including eUK) as well as the leading control manufacturers, such as cPanel and DirectAdmin.
If your looking to use Linux simply in a desktop manner then I would stick with Ubuntu or use Gentoo.
Thomas mentioned Fedora Core; this is a very powerful system but may not always be the best to use in a server environment.
You also mentioned that the network people at your workplace said Windows was the way to go. I wouldn't disagree with this, however if you are going to go with Windows I would highly suggest a
VPS Hosting. This is because if you have a home server or a dedi then you are responsible for applying the Microsoft updates; if you go for a
VPS Hosting then the hosting company are responsible for the updates as they normally do them on the main node which then take affect accross all the
VPS Hosting.