File upload boxes is where we're currently at if you don't want to involve other technologies like Flash, Java or ActiveX.
If you are willing to use Flash (which is available pretty much anywhere and on many platforms), you can overcome pretty much all of these problems. A quick googling turned up two such components, both of them free and open source. I never used any of them, but they look good. BTW, Flash isn't without its problems either, for example when using the multi-file uploader for slide share, the browser kept constantly crashing on me :-(
Probably the best solution currently is to detect dynamically if the user has Flash, and if it's the case, give her the flash version of the uploader, while still making it possible to choose the basic HTML one.