Asking for something that supports most of that by default is asking a lot. However, my preferences have always lied in Debian. There is a package for general packet shaping, and I think it supports basic QoS. It's called
cbq.init; the Debian package is called
shaper. I haven't used it, but I've been told it works very well.
Also, I know it's a Linux forum, but OpenBSD is renowned as a gateway firewall and router. PF [OpenBSD's packet filtering subsystem] is very robust, and if I recall correctly, supports QoS natively. It's worth a look. I've also heard it scales well. However, I don't have much experience concerning those aspects of it, so YMMV.