I'm running a HTTP proxy for a college and can tell you from experience: HTTP is your answer. You want to support it first, because it's used more widely. Also, if you support HTTPS (and therefor CONNECT argument for HTTP Proxy) you can delay Socks a bit. Most times its just the "kids" (be they 20 or 50yrs old) who want to connect with their messaging servers (ICQ/AOL, Jabber, ...) and this can be easily solved if you can configure CONNECT to different ports. Additionally, you should be able to supply a PAC-File from your software, makes life for your clients easier.
IF you support HTTP and code the stuff yourself, please look at ICP and using Cache Peers so people can use some Squid for caching too :-)