There would be a free portion of the available bandwidth and everyone who submits shares or buys credits can then get an additional certain bandwidth for a certain time guaranteed (for example: 1 share = 1 kB/s for 1 hour).
Just pay for the bandwidth you want to have either via Bitcoin or mining shares (can even be accumulated over time) and start downloading right away. As the really expensive part is anyways traffic, you could even offer bindings to (at least) BitTorrent and ed2k via magnet links, if some people prefer P2P. Both protocols also can download via HTTP afaik, so the same system would work there as well (you can choose to pay for a seeder just for you).
As the whole thing should be Bitcoin financed, there would be no need for ads or other stupid stuff. It might even be possible to throw together a nice GUI for a miner that is hardwired to that site!
The only thing I'm missing currently are easily scriptable QoS/traffic control/traffic shaping programs (which run on other platforms than Linux too...). The best I found till now seems to be http://www.freenet.org.nz/python/pyshaper/ - maybe you know some alternatives? I'd be especially interested in having a more "integrated" approach, ideally a general python module/library. Shaping would most likely need to be done anyways just for outgoing transactions.