Bandwidth size depends on the business of your company and number of users, both internal and external. If your company has a large internet presence providing service over the internet to the public then you will need more. If you use your internet connection primarily for user access to the internet then a T1 is generally adequate.
The traffic will definitely be cut down significantly if bandwidth controls are put in. If the VPs are genuinely interested in blocking unauthorized traffic there are two things that need to be done.
1. Have an explicity internet usage document that every existing employee signs and is put into every new employee's paperwork package. This doc spells out *exactly* what is and isn't considered proper usage of the company's internet link. Since your company is paying for the pipe they should have guidelines as to what happends on it. This is necessary not only from a resource standpoint but from a legal standpoint too (if some users *are* going to "xxx.com" et al. it's only a matter of time before someone shouts "harrassment" and the company's in court).
2. Put in technology to enforce number 1. Things like firewalls (which you should have anyway) control protocols and ports access. The log files from the firewall will give a good idea of what is floating across your internet link, since many applications use specific port numbers, for instance realplayer uses 7070 (a google search usually turns up the ones you don't know).
Thereare also applications like WebSense, SurfControl et al. that have databases of sites classified by content and can be configured to block user access.
For all the naysayers that say "technology is not the ultimate solution," well, of course it's not. The point is to have an explicitly defined policy that is known to be enforced to a point. Those who know they are being watched generally behave more responsibly.